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
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

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