Dijkstra's algorithm proof 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)
 A: 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". 
