Does dijkstras algorithm relax the edges of the shortest path in order?

Question

In "Introduction to algorithms, 3rd edition" exercise 24.3-5 wants an example that this is wrong (not always true). Is that possible? In my mind this is impossible because every edge is relaxed at a time when the path to the current vertice is already decided.

Word for word:

Professor N. claims to have a proof of correctness of Dijkstra's algorithm. He claims that Dijkstra's algorithm relaxes the edges of every shortest path in the graph in the order in which they appear on the path, and therefore the path-relaxation property applies to every vertex reachable from the source. Show the professor is mistaken by constructing a directed graph for which Dijkstra's algorithm could relax the edges of a shortest path out of order.

Answer 1

Produce a single edge, weight three, that reaches the destination. Now add a path consisting of several stops, total weight less than three, that also reach the destination. When you relax the origin, you'll color the destination node as three, which is wrong. You have to continue relaxing all nodes closer than (min known path to destination) until that set is empty. Only then can you be sure D's algorithm has given you the correct answer.

Look up A* algorithm for more fun.

Answer 2

The point is that the conclusion doesn't follow from the premises, and to construct a counterexample. SSSP finds all shortest paths. There is no reason that shortest-paths need be found in strict order. Consider a tree-graph. All paths are also shortest. Now, if we relax the root, then there is no particular ordering on the edges. But suppose you even imposed one. Then after relaxing the closest non-root node, you might have a bunch of really long edges to the second tier. The next closest root-neighbor might have a bunch of really short outbound edges to that portion of the second tier. In that case, you'll relax edges that contribute to a total path length SHORTER than other edges you'd already relaxed, since you always relax NODES, not edges, in shortest-path order.