1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
(*
* This module implements the Floyd/Warshall algorithm for computing
* all pairs shortest paths.
*
* -- Allen
*)
functor FloydWarshall(Num : ABELIAN_GROUP_WITH_INF)
: ALL_PAIRS_SHORTEST_PATHS =
struct
structure Num = Num
structure G = Graph
structure A = Array2
fun all_pairs_shortest_paths{graph=G.GRAPH G,weight} =
let val N = #capacity G ()
val D = A.array(N,N,Num.inf)
val P = A.array(N,N,~1)
fun init() =
let fun diag ~1 = ()
| diag i = (A.update(D,i,i,Num.zero); diag(i-1))
in diag(N-1);
#forall_edges G (fn e as (i,j,_) =>
let val w = weight e
in if Num.<(w,A.sub(D,i,j)) then
(A.update(P,i,j,i); A.update(D,i,j,w))
else ()
end)
end
fun l1(k) = if k < N then (l2(k,0); l1(k+1)) else ()
and l2(k,i) = if i < N then (l3(k,i,0,A.sub(D,i,k)); l2(k,i+1)) else ()
and l3(k,i,j,d_ik) = if j < N then
let val d_ij = A.sub(D,i,j)
val d_kj = A.sub(D,k,j)
val x = Num.+(d_ik,d_kj)
in if Num.<(x,d_ij) then
(A.update(P,i,j,A.sub(P,k,j)); A.update(D,i,j,x))
else ();
l3(k,i,j+1,d_ik)
end else ()
in init();
l1(0);
{dist=D,pred=P}
end
end
|
