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
|
(*
* Signatures for shortest paths problems
*
* -- Allen
*)
signature SINGLE_SOURCE_SHORTEST_PATHS =
sig
structure Num : ABELIAN_GROUP_WITH_INF
val single_source_shortest_paths :
{ graph : ('n,'e,'g') Graph.graph,
weight : 'e Graph.edge -> Num.elem,
s : Graph.node_id
} ->
{ dist : Num.elem Array.array,
pred : Graph.node_id Array.array
}
end
signature ALL_PAIRS_SHORTEST_PATHS =
sig
structure Num : ABELIAN_GROUP_WITH_INF
val all_pairs_shortest_paths :
{ graph : ('n,'e,'g') Graph.graph,
weight : 'e Graph.edge -> Num.elem
} ->
{ dist : Num.elem Array2.array,
pred : Graph.node_id Array2.array
}
end
|
