Single-Source Shortest Paths: Dijkstra’s Algorithm

Posted By on March 19, 2016


Download PDF
Minimum Spanning Tree: Prim's Algorithm
All-Pairs Shortest Paths

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 (VVT ), Dijkstra’s algorithm stores l[u], the minimum cost to reach vertex u from vertex s by means of vertices in VT; Prim’s algorithm stores d [u], the cost of the minimum-cost edge connecting a vertex in VT to u. The run time of Dijkstra’s algorithm is Q(n2).

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.

Minimum Spanning Tree: Prim's Algorithm
All-Pairs Shortest Paths

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com