Class MartinShortestPath<V,​E>

  • Type Parameters:
    V - the vertex type
    E - the edge type
    All Implemented Interfaces:
    MultiObjectiveShortestPathAlgorithm<V,​E>

    public class MartinShortestPath<V,​E>
    extends java.lang.Object
    Martin's algorithm for the multi-objective shortest paths problem.

    Martin's label setting algorithm is a multiple objective extension of Dijkstra's algorithm, where the minimum operator is replaced by a dominance test. It computes a maximal complete set of efficient paths when all the cost values are non-negative.

    Note that the multi-objective shortest path problem is a well-known NP-hard problem.

    Author:
    Dimitrios Michail
    • Field Detail

      • graph

        protected final Graph<V,​E> graph
        The underlying graph.
    • Constructor Detail

      • MartinShortestPath

        public MartinShortestPath​(Graph<V,​E> graph,
                                  java.util.function.Function<E,​double[]> edgeWeightFunction)
        Create a new shortest path algorithm
        Parameters:
        graph - the input graph
        edgeWeightFunction - the edge weight function
    • Method Detail

      • getPaths

        public java.util.List<GraphPath<V,​E>> getPaths​(V source,
                                                             V sink)
        Description copied from interface: MultiObjectiveShortestPathAlgorithm
        Get a shortest path from a source vertex to a sink vertex.
        Parameters:
        source - the source vertex
        sink - the target vertex
        Returns:
        a shortest path or null if no path exists
      • createEmptyPath

        protected final GraphPath<V,​E> createEmptyPath​(V source,
                                                             V sink)
        Create an empty path. Returns null if the source vertex is different than the target vertex.
        Parameters:
        source - the source vertex
        sink - the sink vertex
        Returns:
        an empty path or null null if the source vertex is different than the target vertex