Package org.jgrapht.alg.shortestpath
Class MartinShortestPath<V,E>
- java.lang.Object
-
- org.jgrapht.alg.shortestpath.MartinShortestPath<V,E>
-
- Type Parameters:
V
- the vertex typeE
- 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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MultiObjectiveShortestPathAlgorithm
MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths<V,E>
-
-
Constructor Summary
Constructors Constructor Description MartinShortestPath(Graph<V,E> graph, java.util.function.Function<E,double[]> edgeWeightFunction)
Create a new shortest path algorithm
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected GraphPath<V,E>
createEmptyPath(V source, V sink)
Create an empty path.MultiObjectiveShortestPathAlgorithm.MultiObjectiveSingleSourcePaths<V,E>
getPaths(V source)
Compute all shortest paths starting from a single source vertex.java.util.List<GraphPath<V,E>>
getPaths(V source, V sink)
Get a shortest path from a source vertex to a sink vertex.
-
-
-
Field Detail
-
graph
protected final Graph<V,E> graph
The underlying graph.
-
-
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 vertexsink
- 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 interfaceMultiObjectiveShortestPathAlgorithm<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 vertexsink
- the sink vertex- Returns:
- an empty path or null null if the source vertex is different than the target vertex
-
-