For each unsettled node y, we record the length of the shortest special path from x yo y. A special path is one consisting entirely of edges between settled nodes except for the last edge which connects some setled node with y. Now we proceed to loop until all nodes than can be settled are settled. We will trace the execution of Dijkstra's algorithm for the following graph. Initially, we have the following values for dist.
Bold values mean that the node is settled.
On the first iteration we pick Salt Lake because it has the minimum dist among unsettled nodes. The following table shows the changes made in each iteration. That nonspecial path existed before y was settled and must consist of a special path from s to some node z followed by a path from z to y as shown below. This is our contradiction. We need to look at two cases to see if the same property holds for x after settling y. Case 1.