1
$\begingroup$

enter image description here

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 .

$\endgroup$
3
  • $\begingroup$ 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)$. $\endgroup$
    – Gerry Myerson
    Jun 16, 2014 at 9:47
  • $\begingroup$ Oh , I understand it now , should I delete the question ? $\endgroup$
    – abkds
    Jun 16, 2014 at 9:51
  • 2
    $\begingroup$ Why not write up an answer, and post it? $\endgroup$
    – Gerry Myerson
    Jun 16, 2014 at 9:54

1 Answer 1

Reset to default
5
$\begingroup$

[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)$.

$\endgroup$
4
  • $\begingroup$ I'd say proving rigorously that an algorithm works is really boring, thinking instead at an higher level to "how to explain intuitively in simple words that it works" with drawings and examples is much more relevant. $\endgroup$
    – reuns
    May 21, 2016 at 3:44
  • 1
    $\begingroup$ 1) "boring" and "relevant" are not antonyms. 2) Explaining in simple words that something works is always difficult, often impossible, and sometimes just plain wrong ("There is no problem so difficult that it doesn't have a solution that is simple, elegant, and wrong"). $\endgroup$
    – Gerry Myerson
    May 21, 2016 at 3:51
  • $\begingroup$ I could add too : proving that an algorithm works on a paper, without running it, is un-natural. The nature of algorithm is that the natural way for proving they work is while running them. You see what I mean ? $\endgroup$
    – reuns
    May 21, 2016 at 4:12
  • 2
    $\begingroup$ @user, what about an algorithm that works only 99% of the time? You could convince yourself that it works by running it, if you're lucky enough to miss the 1% of cases where it fails, but you'd be wrong. $\endgroup$
    – Gerry Myerson
    May 21, 2016 at 4:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .