10.3 Single-Source Shortest Paths: Dijkstra's Algorithm

For a weighted graph G = (V, E, w), the single-source shortest paths problem is to find the shortest paths from a vertex v V to all other vertices in V. A shortest path from u to v is a minimum-weight path. Depending on the application, edge weights may represent time, cost, penalty, loss, or any other quantity that accumulates additively along a path and is to be minimized. In the following section, we present Dijkstra's algorithm, which solves the single-source shortest-paths problem on both directed and undirected graphs with non-negative weights.

Dijkstra's algorithm, which finds the shortest paths from a single vertex s, is similar to Prim's minimum spanning tree algorithm. Like Prim's algorithm, it incrementally finds the shortest paths from s to the other vertices of G. It is also greedy; that is, it always chooses an edge to a vertex that appears closest. Algorithm 10.2 shows Dijkstra's algorithm. Comparing this algorithm with Prim's minimum spanning tree algorithm, we see that the two are almost identical. The main difference is that, for each vertex u (V - V_T ), Dijkstra's algorithm stores l[u], the minimum cost to reach vertex u from vertex s by means of vertices in V_T; Prim's algorithm stores d [u], the cost of the minimum-cost edge connecting a vertex in V_T to u. The run time of Dijkstra's algorithm is Q(n²).

Algorithm 10.2 Dijkstra's sequential single-source shortest paths algorithm.

1.   procedure DIJKSTRA_SINGLE_SOURCE_SP(V, E, w, s) 
2.   begin 
3.      VT := {s}; 
4.      for all v  (V - VT ) do 
5.         if (s, v) exists set l[v] := w(s, v); 
6.         else set l[v] := ; 
7.      while VT  V do 
8.      begin 
9.         find a vertex u such that l[u] := min{l[v]|v  (V - VT )}; 
10.        VT := VT  {u}; 
11.        for all v  (V - VT ) do 
12.            l[v] := min{l[v], l[u] + w(u, v)}; 
13.     endwhile 
14.  end DIJKSTRA_SINGLE_SOURCE_SP 

Parallel Formulation

The parallel formulation of Dijkstra's single-source shortest path algorithm is very similar to the parallel formulation of Prim's algorithm for minimum spanning trees (Section 10.2). The weighted adjacency matrix is partitioned using the 1-D block mapping (Section 3.4.1). Each of the p processes is assigned n/p consecutive columns of the weighted adjacency matrix, and computes n/p values of the array l. During each iteration, all processes perform computation and communication similar to that performed by the parallel formulation of Prim's algorithm. Consequently, the parallel performance and scalability of Dijkstra's single-source shortest path algorithm is identical to that of Prim's minimum spanning tree algorithm.