# Functor Path.BellmanFord

`module BellmanFord: `functor (``G`` : ``G``) -> ``functor (``W`` : ``Sig.WEIGHT``  with type edge = G.E.t``) -> ``sig` .. `end``
Parameters:
 `G` : `G` `W` : `Sig.WEIGHT with type edge = G.E.t`

`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)