Functor Path.BellmanFord

module BellmanFord: 
functor (G : G) -> 
functor (W : WEIGHT  with type label = G.E.label) -> sig .. end

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 negative-length 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 negative-length 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 negative-length cycle in graph g and returns it. If the graph g is free from such a cycle, raises Not_found.

Complexity: O(V^2E)