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
        end
      val iter_vertex : (V.t -> unit) -> Path.G.t -> unit
      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 type WEIGHT =
    sig
      type label
      type t
      val weight : Path.WEIGHT.label -> Path.WEIGHT.t
      val compare : Path.WEIGHT.t -> Path.WEIGHT.t -> int
      val add : Path.WEIGHT.t -> Path.WEIGHT.t -> Path.WEIGHT.t
      val zero : Path.WEIGHT.t
    end
  module Dijkstra :
    functor (G : G->
      functor
        (W : sig
               type label = G.E.label
               type t
               val weight : label -> 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 label = G.E.label
               type t
               val weight : label -> 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 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