SCM Repository
[smlnj] / MLRISC / trunk / graphs / dijkstra.sml |
View of /MLRISC/trunk/graphs/dijkstra.sml
Parent Directory | Revision Log
Revision 412 -
(download)
(annotate)
Fri Sep 3 00:25:03 1999 UTC (20 years, 3 months ago) by monnier
Original Path: sml/trunk/src/MLRISC/graphs/dijkstra.sml
File size: 1082 byte(s)
Fri Sep 3 00:25:03 1999 UTC (20 years, 3 months ago) by monnier
Original Path: sml/trunk/src/MLRISC/graphs/dijkstra.sml
File size: 1082 byte(s)
This commit was generated by cvs2svn to compensate for changes in r411, which included commits to RCS files with non-trunk default branches.
(* * This module implements the Dijkstra algorithm for computing * the single source shortest paths. * * -- Allen *) functor DijkstraFn(Num : ABELIAN_GROUP_WITH_INF) : SINGLE_SOURCE_SHORTEST_PATHS = struct structure Num = Num structure Q = NodePriorityQueueFn(Array) structure G = Graph structure A = Array fun single_source_shortest_paths{ graph=G' as G.GRAPH G, weight, s } = let val N = #capacity G () val dist = A.array(N, Num.inf) val pred = A.array(N, ~1) val Q = Q.fromGraph (fn (i,j) => Num.<(A.sub(dist,i),A.sub(dist,j))) G' fun relax(e as (u,v,_)) = let val d_v = A.sub(dist,v) val d_x = Num.+(A.sub(dist,u),weight e) in if Num.<(d_x,d_v) then (A.update(dist,v,d_x); A.update(pred,v,u); Q.decreaseWeight(Q,v)) else () end in A.update(dist,s,Num.zero); (while true do app relax (#out_edges G (Q.deleteMin Q)) ) handle Q.EmptyPriorityQueue => (); { dist = dist, pred = pred } end end
root@smlnj-gforge.cs.uchicago.edu | ViewVC Help |
Powered by ViewVC 1.0.0 |