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 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/graphs/dijkstra.sml

1 : monnier 245 structure Dijkstra : SINGLE_SOURCE_SHORTEST_PATHS =
2 :     struct
3 :    
4 :     structure Q = NodePriorityQueueFn(Array)
5 :     structure G = Graph
6 :     structure A = Array
7 :    
8 :     fun single_source_shortest_paths { weight, <, +, inf, zero } =
9 :     let fun dijkstra (G' as G.GRAPH G) s =
10 :     let val N = #capacity G ()
11 :     val dist = A.array(N, inf)
12 :     val pi = A.array(N, ~1)
13 :     val _ = A.update(dist,s,zero)
14 :     fun less(i,j) = A.sub(dist,i) < A.sub(dist,j)
15 :     val Q = Q.fromGraph less G'
16 :     fun relax(e as (u,v,_)) =
17 :     let val d_v = A.sub(dist,v)
18 :     val d_x = A.sub(dist,u) + weight e
19 :     in if d_x < d_v then
20 :     (A.update(dist,v,d_x);
21 :     A.update(pi,v,u);
22 :     Q.decreaseWeight(Q,v))
23 :     else ()
24 :     end
25 :     in
26 :     (while true do
27 :     app relax (#out_edges G (Q.deleteMin Q))
28 :     ) handle Q.EmptyPriorityQueue => ();
29 :     { dist = dist,
30 :     pred = pi
31 :     }
32 :     end
33 :     in
34 :     dijkstra
35 :     end
36 :    
37 :     end

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