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.

• A "greedy" algorithm always makes the locally optimal choice under the assumption that this will lead to an optimal solution overall.

• Example: in making change using the fewest number of coins, always start with the largest coin possible.

Data structures used by Dijkstra's algorithm include:

• a cost matrix C, where C[i,j] is the weight on the edge connecting node i to node j. If there is no such edge, C[i,j] = infinity.

• a set of nodes S, containing all the nodes whose shortest path from the source node is known. Initially, S contains only the source node.

• a distance vector D, where D[i] contains the cost of the shortest path (so far) from the source node to node i, using only those nodes in S as intermediaries.

The Algorithm

  
  DijkstraSSSP (int N, rmatrix &C, vertex v, rvector &D)
  {
     set S;
     int i;
     vertex k, w;
     float cw;
  
     Insert(S,v);
     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

• D[x] would be less than D[w]

• x would be selected before w

• x would be in S

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 first nested loop is O(N) since we examine each vertex to determine whether or not it is in V-S.

   • The second nested loop is O(N) since we examine each vertex to determine whether or not it is in V-S.

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

• Use an adjacency list representation for the graph

• Maintain the set of nodes V-S as a priority queue

  • a partially ordered tree implementation of the priority queue allows updates in O(log N)

The new analysis is

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

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

   • The first nested loop is DeleteMin on the priority queue, which is O(log N).

   • Since each edge is considered at most once in the second nested loop (over the whole execution), and each access to the priority queue requires O(log N), the entire time spent in this loop is O(|E| log N).

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.