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

SCM Repository

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

View of /sml/trunk/src/MLRISC/graphs/dijkstra.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (download) (annotate)
Sat Apr 17 18:47:12 1999 UTC (21 years, 3 months ago) by monnier
Original Path: sml/branches/SMLNJ/src/MLRISC/graphs/dijkstra.sml
File size: 1088 byte(s)
version 110.16
structure Dijkstra : SINGLE_SOURCE_SHORTEST_PATHS =
struct

   structure Q = NodePriorityQueueFn(Array)
   structure G = Graph
   structure A = Array

   fun single_source_shortest_paths { weight, <, +, inf, zero } =
   let fun dijkstra (G' as G.GRAPH G) s =
       let val N    = #capacity G ()
           val dist = A.array(N, inf)
           val pi   = A.array(N, ~1)
           val _    = A.update(dist,s,zero)
           fun less(i,j) = A.sub(dist,i) < A.sub(dist,j)
           val Q  = Q.fromGraph less G'
           fun relax(e as (u,v,_)) =
           let val d_v = A.sub(dist,v)
               val d_x = A.sub(dist,u) + weight e
           in  if d_x < d_v then 
                  (A.update(dist,v,d_x); 
                   A.update(pi,v,u); 
                   Q.decreaseWeight(Q,v))
               else ()
           end
       in  
           (while true do
              app relax (#out_edges G (Q.deleteMin Q))
           ) handle Q.EmptyPriorityQueue => ();
           { dist = dist,
             pred = pi
           }
       end
   in
       dijkstra
   end
        
end

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