Lecture
Dijkstra's algorithm — a graph algorithm invented by the Dutch scientist E. Dijkstra in 1959. It finds the shortest distance from one of the vertices of a graph to all the others. The algorithm works only for graphs without edges of negative weight.
In line 1, the usual initialization of the values d and pi is performed, and in line 2 the empty set of vertices S is initialized. This algorithm maintains an invariant according to which, at the beginning of each iteration of the while loop in lines 4-8, the equality Q = V — S holds. In line 3, the non-decreasing priority queue Q is initialized so that it contains all vertices of the set V; since at that moment S = 0, after line 3 is executed the invariant stated above holds. At each iteration of the while loop in lines 4-8, a vertex u is extracted from the set Q = V — S and added to the set S, as a result of which the invariant continues to be maintained. (During the first iteration of this loop, u = s.) Thus, vertex u has the minimum shortest-path estimate among all vertices of the set V — S. Then, in lines 7-8, all edges (u, v) leaving vertex u are relaxed. If the current shortest path to vertex v can be improved by passing through vertex u, relaxation is performed and the estimate of the value d[v] and the predecessor pi[v] are updated accordingly. Note that after line 3 is executed, vertices are never added to the set Q, and each vertex is extracted from this set and added to the set S exactly once, so the number of iterations of the while loop in lines 4-8 equals |V|. Since Dijkstra's algorithm always selects from the set V — S the "lightest," or "closest," vertex to place into set S, this algorithm is said to follow a greedy strategy.
The running time of Dijkstra's algorithm depends on the implementation of the non-decreasing priority queue. First, consider the case where the non-decreasing priority queue is maintained by numbering all vertices from 1 to |V|. The attribute d[v] is simply placed in an array element with index v. Each Insert and Decrease_Key operation (implicitly present in the Relax procedure) takes time O(1), while each Extract_Min operation takes time O(V) (since it searches through the entire array); as a result, the total running time of the algorithm equals O(V2 + E) = O(V2).
If the graph is sufficiently sparse, in particular if the number of vertices and edges in it are related by E = o(V2/lgV), it is practically advisable to implement the non-decreasing priority queue as a binary non-decreasing heap. (An important implementation detail is that vertices and their corresponding heap elements must maintain references to each other.) Furthermore, each Extract_Min operation takes time O(lg V), and as before there are |V| such operations. The time required to build the non-decreasing heap equals O(V). Each Decrease_Key operation takes time O(lgV), and at most |E| such operations are performed in total. Therefore, the total running time of the algorithm equals O((V + E) lg V), which equals O(E*lg V) if all vertices are reachable from the source. This running time turns out to be better than that of the direct implementation O(V2) when E = o(V2/lg V).
Comments