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 412 - (download) (annotate)
Fri Sep 3 00:25:03 1999 UTC (19 years, 10 months ago) by monnier
File size: 1082 byte(s)
This commit was generated by cvs2svn to compensate for changes in r411,
which included commits to RCS files with non-trunk default branches.
(*
 * This module implements the Dijkstra algorithm for computing
 * the single source shortest paths.
 *
 * -- Allen
 *)

functor DijkstraFn(Num : ABELIAN_GROUP_WITH_INF) 
     : SINGLE_SOURCE_SHORTEST_PATHS =
struct

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

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

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