I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and $l_e$ is the shortest path to some $u$ in unexplored part followed by a single edge $(u,v)$ . Now in the proof I understand the 'nonnegative weights' and the conclusion drawn from it , similarly I understood the 'inductive hypothesis' conclusion and 'defn of $\pi(y)$' but I am unable to understand the 'Dijkstra chose v instread of y' , which completes the proof . Please can anyone explain me that .
Best Answer
[I invited OP to write up an answer, and to post it, but OP has not taken up this suggestion, so I'm posting my comment as an answer.]
In terms of your diagram, the algorithm has already found the shortest path from $s$ to $x$ and to $u$, and decides to add the edge joining $u$ to $v$ instead of the edge joining $x$ to $y$ --- that is, it chose $v$ instead of $y$ --- because $\pi(v)\le\pi(y)$.