/* dijkstra.q: Dijkstra's shortest path algorithm 10-21-01 AG */
import bag, dict, graph;
/* Dijkstra's shortest path algorithm: compute the shortest path between node
S and T in a weighted graph G. The weights are taken from the first label
of each edge (a default weight of 1 is assumed for unlabelled edges). The
algorithm either returns the shortest path and its length, or infinity if
no path exists. */
public dijkstra G S T;
private search G S T ST, search2 G S T ND ST;
private queue DIST, head Q, rmhead Q, change Q N D1 D2;
dijkstra G:Graph S:Int T:Int
= search G S T (Q, DIST, PRED)
where V = nodes G, DIST = insert (mkdict inf V) (S,0),
Q = queue (members DIST), PRED = emptydict
if member G S and then member G T;
/* The search loop. It takes as input the following parameters:
- Graph G, source node S and target node T.
- A queue Q of node-distance pairs waiting to be processed, ordered by
increasing distances from the source.
- A dictionary DIST which stores all current distances from the source.
Initially, all distances are infinite, except the distance of S itself
which is 0.
- A dictionary PRED which keeps track of the predecessor nodes in the
shortest path tree. This data is used to reconstruct the shortest path
when we are finished.
In each iteration we process the node N at the beginning of the queue. This
is the node which currently is at the smallest distance from the source;
initially this will be S itself. We remove N from the queue and update
the distances in Q, DIST and the predecessor links in PRED accordingly, by
checking which distances are reduced by traversing the outgoing edges of
N. The algorithm terminates as soon as we hit the target node T (in which
case the path is built by following the predecessor links from T back to S)
or when the next available node is at infinite distance (which indicates
that the target node cannot be reached from the source). */
search G S T (Q,DIST,PRED)
= search2 G S T (head Q) (rmhead Q,DIST,PRED);
private check_edge ND ST E, weight E;
search2 G S T (N,D) (Q,DIST,PRED)
= inf if D=inf;
= ([S|reverse (while (<>S) (PRED!) T)],D) if N=T;
= search G S T
(foldl (check_edge (N,D)) (Q,DIST,PRED) (edges (G!N)))
otherwise;
/* Process outgoing edges of the current node and update (Q,DIST,PRED)
accordingly. */
check_edge (N,D) (Q,DIST,PRED) E
= (change Q M D1 D2, update DIST M D2, update PRED M N)
if D2 < D1
where M = target E, D1 = DIST!M, D2 = D+weight E;
= (Q,DIST,PRED) otherwise;
/* Extract the weight from an edge. */
weight (_,_,W:Real|_)
= W;
weight _ = 1 otherwise;
/* The node queue is implemented as a bag. By exchanging the node and distance
values and encoding the pairs as lists we ensure that the bag is kept
sorted by the distance values (using the lexicographic list order). */
/* Initialize the queue from a list of node-priority pairs. */
var N, D;
queue DIST = bag (map (lambda (N,D) [D,N]) DIST);
/* The head element of the queue. */
head Q = (N,D) where [D,N] = first Q;
/* Remove the head element from the queue. */
rmhead Q = rmfirst Q;
/* Change the priority of an element in the queue. */
change Q N D1 D2 = insert (delete Q [D1,N]) [D2,N];