Single Source Shortest Path (SSSP) Problem

Given a directed graph G = (V,E), with non-negative costs on each edge, and a selected source node v in V, for all w in V, find the cost of the least cost path from v to w.

The cost of a path is simply the sum of the costs on the edges traversed by the path.

This problem is a general case of the more common subproblem, in which we seek the least cost path from v to a particular w in V. In the general case, this subproblem is no easier to solve than the SSSP problem.

Dijkstra's Algorithm

Dijkstra's algorithm is a greedy algorithm for the SSSP problem.

Data structures used by Dijkstra's algorithm include:

The Algorithm

  DijkstraSSSP (int N, rmatrix &C, vertex v, rvector &D)
     set S;
     int i;
     vertex k, w;
     float cw;
     for (k = 0; k < N; k++) D[k] = C[v][k];
     for (i = 1; i < N; i++) {
         /* Find w in V-S st. D[w] is minimum */
         cw = INFINITY;
         for (k = 0; k < N; k++)
  	  if (! Member(S,k) && D[k] < cw) {
  	     cw = D[k];
  	     w = k;
         Insert(S, w);
         /* Forall k not in S */
         for (k = 0; k < N; k++)
  	  if (! Member(S,k))
               /* Shorter path from v to k using w? */
  	     if (D[w] + C[w][k] < D[k])
  		D[k] = D[w] + C[w][k];
  } /* DijkstraSSSP */

How Dijkstra's Algorithm Works

On each iteration of the main loop, we add vertex w to S, where w has the least cost path from the source v (D[w]) involving only nodes in S.

We know that D[w] is the cost of the least cost path from the source v to w (even though it only uses nodes in S).

If there is a lower cost path from the source v to w going through node x (where x is not in S) then

Analysis of Dijkstra's Algorithm

Consider the time spent in the two loops:

  1. The first loop has O(N) iterations, where N is the number of nodes in G.

  2. The second (and outermost) loop is executed O(N) times.

The algorithm is O(N^2).

If we assume that there are many fewer edges than the maximum possible, we can do better than this, however.

Analysis of Dijkstra's Algorithm (cont)

Assume the following implementation details

The new analysis is

  1. The first loop still has O(N) iterations.

  2. The second loop is still executed O(N) times.

  3. The algorithm is O(|E| log N + N log N).

For N <= |E| <= N^2 the result is O(|E| log N), which is much better than O(N^2) in many cases.