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