Signature for edges' weights.
Type for labels of graph edges.
Type of edges' weights.
shortest_path g v1 v2 computes the shortest path from vertex
v2 in graph
g. The path is returned as the list of
followed edges, together with the total length of the path.
Not_found if the path from
v2 does not exist.
Complexity: at most O((V+E)log(V))
shortest_path g vs computes the distances of shortest paths
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
g contains a
negative-length cycle reachable from
NegativeCycle l where
l is such a cycle.
Complexity: at most O(VE)
Check for a path.
the abstract data type of a path checker; this is a mutable data structure
check_path pc v1 v2 checks whether there is a path from
v2 in the graph associated to the path checker
Complexity: The path checker contains a cache of all results computed so far. This cache is implemented with a hash table so access in this cache is usually O(1). When the result is not in the cache, Dijkstra's algorithm is run to check for the path, and all intermediate results are cached.
Note: if checks are to be done for almost all pairs of vertices, it
may be more efficient to compute the transitive closure of the graph