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 /sml/branches/SMLNJ/src/MLRISC/graphs/dijkstra.sml
 [smlnj] / sml / branches / SMLNJ / src / MLRISC / graphs / dijkstra.sml

# Diff of /sml/branches/SMLNJ/src/MLRISC/graphs/dijkstra.sml

revision 410, Fri Sep 3 00:25:03 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 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 DijkstraFn(Num : ABELIAN_GROUP_WITH_INF)
9         : SINGLE_SOURCE_SHORTEST_PATHS =
10  struct  struct
11
12       structure Num = Num
13     structure Q = NodePriorityQueueFn(Array)     structure Q = NodePriorityQueueFn(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             (while true do             (while true do
31                app relax (#out_edges G (Q.deleteMin Q))                app relax (#out_edges G (Q.deleteMin Q))
32             ) handle Q.EmptyPriorityQueue => ();             ) handle Q.EmptyPriorityQueue => ();
33             { dist = dist,             { dist = dist,
34               pred = pi           pred = pred
35             }             }
36         end         end
in
dijkstra
end
37
38  end  end

Legend:
 Removed from v.410 changed lines Added in v.411