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.
Data structures used by Dijkstra's algorithm include:
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
Consider the time spent in the two loops:
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
The new analysis is
For N <= |E| <= N^2 the result is O(|E| log N), which is much better than O(N^2) in many cases.