| 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 Dijkstra(Num : ABELIAN_GROUP_WITH_INF) |
| 9 |
|
: SINGLE_SOURCE_SHORTEST_PATHS = |
| 10 |
struct |
struct |
| 11 |
|
|
| 12 |
structure Q = NodePriorityQueueFn(Array) |
structure Num = Num |
| 13 |
|
structure Q = NodePriorityQueue(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 |
|
Q.decreaseWeight(Q,s); |
| 31 |
(while true do |
(while true do |
| 32 |
app relax (#out_edges G (Q.deleteMin Q)) |
app relax (#out_edges G (Q.deleteMin Q)) |
| 33 |
) handle Q.EmptyPriorityQueue => (); |
) handle Q.EmptyPriorityQueue => (); |
| 34 |
{ dist = dist, |
{ dist = dist, |
| 35 |
pred = pi |
pred = pred |
| 36 |
} |
} |
| 37 |
end |
end |
|
in |
|
|
dijkstra |
|
|
end |
|
| 38 |
|
|
| 39 |
end |
end |
Parent Directory
| 
Revision Log
| 
Patch
