Module org.jgrapht.core
Package org.jgrapht.alg.shortestpath

Class LabelCorrectingMultiObjectiveShortestPath<V,E>

java.lang.Object
org.jgrapht.alg.shortestpath.LabelCorrectingMultiObjectiveShortestPath<V,E>
Type Parameters:
V - the vertex type
E - the edge type
All Implemented Interfaces:
MultiObjectiveShortestPathAlgorithm<V,E>
public class LabelCorrectingMultiObjectiveShortestPath<V,E> extends Object
A label-correcting algorithm for the multi-objective shortest paths problem.

The algorithm is a multiple objective extension of the Bellman-Ford relaxation process. It maintains a set of non-dominated labels for each vertex and iteratively propagates labels through outgoing edges. A newly generated label is discarded if it is dominated by an existing label at the same vertex. Existing labels dominated by the new label are removed.

Optionally, an approximation tolerance $\varepsilon$ may be provided. In that case labels which are sufficiently close according to the tolerance are also discarded in order to reduce the number of stored labels, and the algorithm computes an approximation of the Pareto set. With a tolerance equal to zero the complete Pareto set is computed.

All objective values must be non-negative.

The label-correcting strategy is described in: A. J. V. Skriver and K. A. Andersen. (2000). A label correcting approach for solving bicriterion shortest-path problems. Computers & Operations Research. 27. 507-524. 10.1016/S0305-0548(99)00037-4.

The approximation of the Pareto set is described in: A. Warburton. (1987). Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems. Operations Research. 35. 70-79. 10.1287/opre.35.1.70.

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

Author:
Mario Fuentes Jimenez

  • Field Details

    • graph

      protected final Graph<V,E> graph
      The underlying graph.

  • Constructor Details

    • LabelCorrectingMultiObjectiveShortestPath

      public LabelCorrectingMultiObjectiveShortestPath(Graph<V,E> graph, Function<E,double[]> edgeWeightFunction)
      Create a new shortest path algorithm which computes the complete Pareto set.
      Parameters:
      graph - the input graph
      edgeWeightFunction - the edge weight function

    • LabelCorrectingMultiObjectiveShortestPath

      public LabelCorrectingMultiObjectiveShortestPath(Graph<V,E> graph, Function<E,double[]> edgeWeightFunction, double epsilon)
      Create a new shortest path algorithm which computes an epsilon-approximation of the Pareto set. A tolerance equal to zero computes the complete Pareto set.
      Parameters:
      graph - the input graph
      edgeWeightFunction - the edge weight function
      epsilon - the approximation tolerance, must be non-negative

  • Method Details

    • getPaths

      public 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

    • getPaths

      public MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths<V,E> getPaths(V source)
      Description copied from interface: MultiObjectiveShortestPathAlgorithm
      Compute all shortest paths starting from a single source vertex.
      Specified by:
      getPaths in interface MultiObjectiveShortestPathAlgorithm<V,E>
      Parameters:
      source - the source vertex
      Returns:
      the shortest paths

    • 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

    • validateEdgeWeightFunction

      protected int validateEdgeWeightFunction(Function<E,double[]> edgeWeightFunction)
      Check the validity of an edge weight function. The function must return a non-null vector of non-negative values of the same length for every edge of the graph.
      Parameters:
      edgeWeightFunction - the edge weight function
      Returns:
      the number of dimensions