Module `Path.Johnson`

Parameters

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

Signature

module HVV : Stdlib.Hashtbl.S with type HVV.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))