Module Path.BellmanFord

Parameters

module G : G
module W : Sig.WEIGHT with type edge = G.E.t

Signature

module H : Hashtbl.S with type key = G.V.t and type 'a t = 'a Hashtbl.Make(G.V).t
exception NegativeCycle of G.E.t list
val all_shortest_paths : 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 : G.t -> G.V.t -> 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 : G.t -> 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)