Dijkstra's Algorithm

File:  da_simple.c

Dijkstra's algorithm computes the shortest paths from a starting vertex, s, to
all other vertices in the graph.  For simplicity, we assume that all vertices
are reachable from s.  The source files dgraph.c and dgraph.h provide graphs
with all vertices reachable from the starting vertex.  Let V be the set of
vertices in the graph.  Dijkstra's algorithm maintains a solution set, S, and a
frontier set, F.  S contains vertices for which the shortest path has been
determined.  F contains vertices that have been visited, but for which the
shortest path is still undetermined.  The set of vertices not in S or F, that
is, V-(S+F), are unexplored (or the unknown world).

Dijkstra's algorithm also maintains an array, d, which stores the current
shortest path distance to each vertex.  If a vertex, v, is in S, then d[v]
holds the determined shortest path distance to that vertex.  Otherwise if v is
in F, then d[v] holds the best shortest path distance so far.  Otherwise if v
is in neither S nor F, d[v] is undefined.

Dijkstra's algorithm is given in pseudo code below.  Note that L(u, v) is the
length of edge (u, v).

S = {s};
F = OUT(s);
for v in OUT(s) { d[v] = length(s, v); }

while F is not empty {
    v = u such that d[u] is minimum among u in F;
    F = F - {v};
    S = S + {v};
    for w in OUT(v) {
        if w is not in S {
            new_dist = d[v] + L(v, w);
            if w is in F {
                d[w] = min(d[w], new_dist);
            }
            else {
                d[w] = new_dist;
                F = F + {w};
            }
        }
    }
}

Dijkstra's algorithm begins with S = {s}, and V = OUT(s).  It then moves the
vertex, v, in F that has minimum distance out of F and into S.  Edges out of V
are followed and distances to vertices, w, in OUT(v) are updated if necessary.
Note that if the vertex w is in S, then its shortest path is already known, so
there is no need for update.  If the vertex w is in F, the currently best
distance for it may be improved.  If the vertex w is not in S or F, then it is
added to F, and assigned a currently best shortest path distance.

The dijkstra() function in the program source file da_simple.c follows the
basic structure of this algorithm.  In this program, the frontier set is
implemented using 1 dimensional arrays.  An array, front[], holds the vertex
numbers of vertices in the frontier set.  An array, p[], which is indexed by
vertex number, holds each vertex's index into the front[] array; that is, each
vertex's position in the front[] array.

If there are j vertices in the frontier set, then array entries front[0] to
front[j-1] are occupied, and the rest are undefined.  When a vertex is added
to the frontier set, front[j] becomes occupied, and j is incremented.  If a
vertex is removed from the frontier set, an entry in front[], say front[i] is
no loner used.  When this happens j is decremented, and front[j] is moved to
front[j].  Note that when vertices are added or removed to or from front[],
corresponding entries in array p[] change.  In order to locate the vertex in F
with minimum distance, we must scan the array entries front[0] to front[j-1],
using them to index d[].

This kind of implementation of Dijkstra's algorithm has O(n^2) time complexity.
More sophisticated implementations of Dijkstra's algorithm exist where the
frontier set is implemented using a heap.  A binary heap implementation has
O(m log n) time complexity.  The Fibonacci and 2-3 heap implementations have
O(m + n log n) time complexity.