Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /MLRISC/trunk/graphs/dijkstra.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (view) (download)

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