Dijkstra in Q

gistfile1.txt

/* dijkstra.q: Dijkstra's shortest path algorithm 10-21-01 AG */

import bag, dict, graph;

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;

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;

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;

weight (_,_,W:Real|_)
		= W;
weight _	= 1 otherwise;

var N, D;
queue DIST			= bag (map (lambda (N,D) [D,N]) DIST);

head Q				= (N,D) where [D,N] = first Q;

rmhead Q			= rmfirst Q;

change Q N D1 D2		= insert (delete Q [D1,N]) [D2,N];