Back

Table of contents

Next

Dijkstra's Algorithm

   Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted directed graph G = (V, E) for the case in which all edge weights are non-negative.

   Dijkstra's algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. That is , for all vertices v belonging to S , we have d[v] = delta(s, v). The algorithm repeatedly selects the vetrx u belonging to V - S with the minimum shortest-path estimate, insets u into S , and relaxes all edges leaving u. In the following implementation , we maintain a priority queue Q that contains all the vertices in V - S, keyed by their d values. The implementation assumes that the graph G is represented by adjacency lists.
 

DIJKSTRA(G, w, s)

   1   INITIALIZE-SINGLE-SOURCE(G,s)
   2   S <- empty
   3   Q <- V[G]
   4   while Q != empty
   5          do u <- EXTRACT-MAX(Q)
   6                S <- S U {u}
   7                for each vertex v belonging to Adj[A]
   8                       do RELAX(u, v, w)

   Line 1 performs the usual initialization of d and parent values, and line 2 initializes the set S to the empty set.
 Line 3 then initializes the priority queue Q to contail all the vertices in V - S = V. Each time through the while loop of lines 4-8, a vertex u is extracted from Q = V - S and inserted into the set S. Vertex  u , therefore has the smallest shortest-path estimate of any vertex in V - S. Then lines 7-8 relax each edge (u, v) leaving u, thus updating the estimate d[v] and the predecessor parent[v] if the shortest path to v can be imporved by going through u.
 

analysis?