Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have problem proving the correctness of Dijkstra's algorithm.

You can read about the proof here:

http://serverbob.3x.ro/IA/DDU0150.html

I don't understand why the distance from s to u (d.u) is smaller than the distrance from s to y (the last and important step of the proof)

share|improve this question
    
Because when you picking the closest vertex from among a set that included both u and y, you picked u. If y was closer you would have picked it instead. Someone else may post a more helpful answer. :-) –  ShreevatsaR Jun 16 '11 at 7:04
    
This question might benefit more on cstheory.stackexchange.com –  Asaf Karagila Jun 16 '11 at 10:48
2  
@Asaf: No, this is not a research-level question. cstheory.stackexchange.com is the equivalent of MathOverflow for the CS researcher community. Non-research-level theoretical computer science questions are welcome here on this website. –  ShreevatsaR Jun 16 '11 at 14:26
add comment

1 Answer 1

up vote 8 down vote accepted

The vertex $u \in V \setminus S$ is just the vertex picked by the algorithm in line 5. This line uses the min-priority queue to choose, out of all the vertices in $V \setminus S$, the one for which the value of $d$ is smallest. Now, $y$ belongs to $V \setminus S$ too. So $d[u] \leq d[y]$.

Let me give you an intuitive way to think of Dijkstra's algorithm:

Think of what would happen if you "spill water" in the source vertex $s$. Water would start spreading simultaneously along the edges emanating from $S$. Let the amount of time it takes a water drop to cross an edge be proportional to its weight (that is - interpret the edge weights as "distances" and assume drops move at a constant speed). Then, for each vertex, the information you would like to have is "when did water first arrive here and where did it come from".

This is what Dijkstra's algorithm simulates. Think of the (continuous) water flow processs I described and consider the events of type "water gets to a certain vertex for the first time". These events can be ordered by their time of occurrence. There are $|V|$ such events (assuming the graph is connected). Each iteration of Dijkstra's algorithm celebrates one such event. Ordering the vertices by the number of the iteration where they where extracted from $Q$ and added to $S$ is the same as ordering them by the "time when water first arrived".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.