Correctness of Dijkstra’s algorithm

A nice prove can be found from [1]:

We have 2 sets of vertices at any step of the algorithm. Set A consists of the vertices to which we have computed the shortest paths. Set B consists of the remaining vertices.

Inductive Hypothesis: At each step we will assume that all previous iterations are correct.

Inductive Step: When we add a vertex V to the set A and set the distance to be dist[V], we must prove that this distance is optimal. If this is not optimal then there must be some other path to the vertex V that is of shorter length.

Suppose this some other path goes through some vertex X in the set B.

Now, since dist[V] <= dist[X] , therefore any other path to V will be atleast dist[V] length, unless the graph has negative edge lengths. From [1]

Reference

[1]https://stackoverflow.com/questions/22891420/why-do-all-pair-shortest-path-algorithms-work-with-negative-weights