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 /MLRISC/trunk/graphs/dijkstra.sml
 [smlnj] / MLRISC / trunk / graphs / dijkstra.sml # View of /MLRISC/trunk/graphs/dijkstra.sml

Fri Sep 3 00:25:03 1999 UTC (20 years, 2 months ago) by monnier
Original Path: sml/branches/SMLNJ/src/MLRISC/graphs/dijkstra.sml
File size: 1082 byte(s)
```version 110.19
```
```(*
* 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
```