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) -> Path.G.t -> '-> '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) -> Path.G.t -> '-> 'a
      val nb_vertex : Path.G.t -> int
    end
  module Dijkstra :
    functor (G : G->
      functor
        (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->
      functor
        (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 -> '-> 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 -> '-> unit
              val mem : 'a t -> key -> bool
              val iter : (key -> '-> unit) -> 'a t -> unit
              val fold : (key -> '-> '-> 'b) -> 'a t -> '-> '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->
      functor
        (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 -> '-> 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 -> '-> unit
              val mem : 'a t -> key -> bool
              val iter : (key -> '-> unit) -> 'a t -> unit
              val fold : (key -> '-> '-> 'b) -> 'a t -> '-> '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