Annotation of /MLRISC/trunk/graphs/dijkstra.sml

Parent Directory | Revision Log

---

Revision 1599 - (view) (download)
Original Path: sml/trunk/src/MLRISC/graphs/dijkstra.sml

1 :	monnier	411	(*
2 :			* This module implements the Dijkstra algorithm for computing
3 :			* the single source shortest paths.
4 :			*
5 :			* -- Allen
6 :			*)
7 :
8 :	george	545	functor Dijkstra(Num : ABELIAN_GROUP_WITH_INF)
9 :	monnier	411	: SINGLE_SOURCE_SHORTEST_PATHS =
10 :	monnier	245	struct
11 :
12 :	monnier	411	structure Num = Num
13 :	george	545	structure Q = NodePriorityQueue(Array)
14 :	monnier	411	structure G = Graph
15 :			structure A = Array
16 :	monnier	245
17 :	monnier	411	fun single_source_shortest_paths{ graph=G' as G.GRAPH G, weight, s } =
18 :			let val N = #capacity G ()
19 :			val dist = A.array(N, Num.inf)
20 :			val pred = A.array(N, ~1)
21 :			val Q = Q.fromGraph (fn (i,j) => Num.<(A.sub(dist,i),A.sub(dist,j))) G'
22 :			fun relax(e as (u,v,_)) =
23 :			let val d_v = A.sub(dist,v)
24 :			val d_x = Num.+(A.sub(dist,u),weight e)
25 :			in if Num.<(d_x,d_v) then
26 :			(A.update(dist,v,d_x); A.update(pred,v,u); Q.decreaseWeight(Q,v))
27 :			else ()
28 :	monnier	245	end
29 :	monnier	411	in A.update(dist,s,Num.zero);
30 :	allenleung	1599	Q.decreaseWeight(Q,s);
31 :	monnier	411	(while true do
32 :			app relax (#out_edges G (Q.deleteMin Q))
33 :			) handle Q.EmptyPriorityQueue => ();
34 :			{ dist = dist,
35 :			pred = pred
36 :			}
37 :	monnier	245	end
38 :
39 :			end

---

root@smlnj-gforge.cs.uchicago.edu	ViewVC Help
Powered by ViewVC 1.0.0