module BellmanFord:
Parameters: 

module H:Hashtbl.S
with type key = G.V.t
exception NegativeCycle of Path.G.E.t list
val all_shortest_paths : Path.G.t > G.V.t > W.t H.t
shortest_path g vs
computes the distances of shortest paths
from vertex vs
to all other vertices in graph g
. They are
returned as a hash table mapping each vertex reachable from
vs
to its distance from vs
. If g
contains a
negativelength cycle reachable from vs
, raises
NegativeCycle l
where l
is such a cycle.
Complexity: at most O(VE)
val find_negative_cycle_from : Path.G.t > G.V.t > Path.G.E.t list
find_negative_cycle_from g vs
looks for a negativelength
cycle in graph g
that is reachable from vertex vs
and
returns it as a list of edges. If no such a cycle exists,
raises Not_found
.
Complexity: at most O(VE).
val find_negative_cycle : Path.G.t > Path.G.E.t list
find_negative_cycle g
looks for a negativelength cycle in
graph g
and returns it. If the graph g
is free from such a
cycle, raises Not_found
.
Complexity: O(V^2E)