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

# SCM Repository

[smlnj] Diff of /MLRISC/trunk/graphs/dijkstra.sml
 [smlnj] / MLRISC / trunk / graphs / dijkstra.sml

# Diff of /MLRISC/trunk/graphs/dijkstra.sml

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

Legend:
 Removed from v.245 changed lines Added in v.1599