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

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

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
```