Dijkstra (ocamlgraph.Graph.Path.Dijkstra)

Parameters

module G : G

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

Signature

val shortest_path : G.t -> G.V.t -> G.V.t -> G.E.t list * W.t

shortest_path g v1 v2 computes the shortest path from vertex v1 to vertex v2 in graph g. The path is returned as the list of followed edges, together with the total length of the path. raise Not_found if the path from v1 to v2 does not exist.

Complexity: at most O((V+E)log(V))