Module Path.Johnson

Parameters

module G : G
module W : WJ with type edge = G.E.t

Signature

module HVV : Hashtbl.S with type key = G.V.t * G.V.t
val all_pairs_shortest_paths : G.t -> W.t HVV.t

all_pairs_shortest_paths g computes the distance of shortest path between all pairs of vertices in g. They are returned as a hash table mapping each pair of vertices to their distance. If g contains a negative-cycle, raises NegativeCycle l where l is such a cycle.

Complexity: at most O(VElog(V))