SKEDSOFT

Discrete Mathematics

Assume that the inductive hypothesis holds for the kth iteration. Let v be the vertex added to S at the (k 1)st iteration, so v is a vertex not in S at the end of the kth iteration with the smallest label (in the case of ties, any vertex with smallest label may be used).

From the inductive hypothesis we see that the vertices in S before the (k 1)st iteration are labeled with the length of a shortest path from a. Also, v must be labeled with the length of a shortest path to it from a. If this were not the case, at the end of the kth iteration there would be a path of length less than Lk(v) containing a vertex not in S [because Lk(v) is the length of a shortest path from a to v containing only vertices in S after the kth iteration]. Let u be the first vertex not in S in such a path. There is a path with length less than Lk(v) from a to u containing only vertices of S. This contradicts the choice of v. Hence, (i) holds at the end of the (k 1)st iteration.

Let u be a vertex not in S after k 1 iterations.A shortest path from a to u containing only elements of S either contains v or it does not. If it does not contain v, then by the inductive hypothesis its length is Lk(u). If it does contain v, then it must be made up of a path from a to v of shortest possible length containing elements of S other than v, followed by the edge from v to u. In this case, its length would be Lk(v) w(v, u). This shows that (ii) is true, because
Lk 1(u) = min{Lk(u),Lk(v) w(v, u)}.
We now state the thereom that we have proved.

THEOREM 1 Dijkstra’s algorithm finds the length of a shortest path between two vertices in a connected simple undirected weighted graph.

We can now estimate the computational complexity of Dijkstra’s algorithm (in terms of additions and comparisons). The algorithm uses no more than n − 1 iterations where n is the number of vertices in the graph, because one vertex is added to the distinguished set at each iteration.We are done if we can estimate the number of operations used for each iteration.We can identify the vertex not in Sk with the smallest label using no more than n − 1 comparisons. Then we use an addition and a comparison to update the label of each vertex not in Sk. It follows that no more than 2(n − 1) operations are used at each iteration, because there are no more than n − 1 labels to update at each iteration. Because we use no more than n − 1 iterations, each using no more than 2(n − 1) operations.