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 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.

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 */

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

Consider the time spent in the two loops:

- The first loop has O(N) iterations,
where N is the number of nodes in G.
- 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 first 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.

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

- The first loop still has O(N) iterations.
- 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).

- The first nested loop is DeleteMin on the
priority queue, which is O(log N).
- 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.