sig
  module type G =
    sig
      type t
      module V : Sig.COMPARABLE
      module E :
        sig
          type t
          type label
          val label : Path.G.E.t -> Path.G.E.label
          val src : Path.G.E.t -> V.t
          val dst : Path.G.E.t -> V.t
          val create : V.t -> Path.G.E.label -> V.t -> Path.G.E.t
        end
      val iter_vertex : (V.t -> unit) -> Path.G.t -> unit
      val fold_vertex : (V.t -> 'a -> 'a) -> Path.G.t -> 'a -> 'a
      val iter_succ : (V.t -> unit) -> Path.G.t -> V.t -> unit
      val iter_succ_e : (Path.G.E.t -> unit) -> Path.G.t -> V.t -> unit
      val fold_edges_e : (Path.G.E.t -> 'a -> 'a) -> Path.G.t -> 'a -> 'a
      val nb_vertex : Path.G.t -> int
    end
  module Dijkstra :
    functor
      (G : G) (W : sig
                     type edge = G.E.t
                     type t
                     val weight : edge -> t
                     val compare : t -> t -> int
                     val add : t -> t -> t
                     val zero : t
                   end) ->
      sig
        val shortest_path :
          Path.G.t -> G.V.t -> G.V.t -> Path.G.E.t list * W.t
      end
  module BellmanFord :
    functor
      (G : G) (W : sig
                     type edge = G.E.t
                     type t
                     val weight : edge -> t
                     val compare : t -> t -> int
                     val add : t -> t -> t
                     val zero : t
                   end) ->
      sig
        module H :
          sig
            type key = G.V.t
            type 'a t
            val create : int -> 'a t
            val clear : 'a t -> unit
            val reset : 'a t -> unit
            val copy : 'a t -> 'a t
            val add : 'a t -> key -> 'a -> unit
            val remove : 'a t -> key -> unit
            val find : 'a t -> key -> 'a
            val find_all : 'a t -> key -> 'a list
            val replace : 'a t -> key -> 'a -> unit
            val mem : 'a t -> key -> bool
            val iter : (key -> 'a -> unit) -> 'a t -> unit
            val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
            val length : 'a t -> int
            val stats : 'a t -> Hashtbl.statistics
          end
        exception NegativeCycle of Path.G.E.t list
        val all_shortest_paths :
          Path.G.t -> G.V.t -> W.t Path.BellmanFord.H.t
        val find_negative_cycle_from : Path.G.t -> G.V.t -> Path.G.E.t list
        val find_negative_cycle : Path.G.t -> Path.G.E.t list
      end
  module type WJ =
    sig
      type edge
      type t
      val weight : edge -> t
      val compare : t -> t -> int
      val add : t -> t -> t
      val zero : t
      val sub : t -> t -> t
    end
  module Johnson :
    functor
      (G : G) (W : sig
                     type edge = G.E.t
                     type t
                     val weight : edge -> t
                     val compare : t -> t -> int
                     val add : t -> t -> t
                     val zero : t
                     val sub : t -> t -> t
                   end) ->
      sig
        module HVV :
          sig
            type key = G.V.t * G.V.t
            type 'a t
            val create : int -> 'a t
            val clear : 'a t -> unit
            val reset : 'a t -> unit
            val copy : 'a t -> 'a t
            val add : 'a t -> key -> 'a -> unit
            val remove : 'a t -> key -> unit
            val find : 'a t -> key -> 'a
            val find_all : 'a t -> key -> 'a list
            val replace : 'a t -> key -> 'a -> unit
            val mem : 'a t -> key -> bool
            val iter : (key -> 'a -> unit) -> 'a t -> unit
            val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
            val length : 'a t -> int
            val stats : 'a t -> Hashtbl.statistics
          end
        val all_pairs_shortest_paths : Path.G.t -> W.t Path.Johnson.HVV.t
      end
  module Check :
    functor
      (G : sig
             type t
             module V : Sig.COMPARABLE
             val iter_succ : (V.t -> unit) -> Path.Check.t -> V.t -> unit
           end) ->
      sig
        type path_checker
        val create : Path.G.t -> Path.Check.path_checker
        val check_path : Path.Check.path_checker -> G.V.t -> G.V.t -> bool
      end
end