Package org.jgrapht.alg
Class DijkstraShortestPath<V,E>
- java.lang.Object
-
- org.jgrapht.alg.DijkstraShortestPath<V,E>
-
public final class DijkstraShortestPath<V,E> extends java.lang.Object
An implementation of Dijkstra's shortest path algorithm usingClosestFirstIterator
.- Since:
- Sep 2, 2003
- Author:
- John V. Sichi
-
-
Constructor Summary
Constructors Constructor Description DijkstraShortestPath(Graph<V,E> graph, V startVertex, V endVertex)
Creates and executes a new DijkstraShortestPath algorithm instance.DijkstraShortestPath(Graph<V,E> graph, V startVertex, V endVertex, double radius)
Creates and executes a new DijkstraShortestPath algorithm instance.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static <V,E>
java.util.List<E>findPathBetween(Graph<V,E> graph, V startVertex, V endVertex)
Convenience method to find the shortest path via a single static method call.GraphPath<V,E>
getPath()
Return the path found.java.util.List<E>
getPathEdgeList()
Return the edges making up the path found.double
getPathLength()
Return the length of the path found.
-
-
-
Constructor Detail
-
DijkstraShortestPath
public DijkstraShortestPath(Graph<V,E> graph, V startVertex, V endVertex)
Creates and executes a new DijkstraShortestPath algorithm instance. An instance is only good for a single search; after construction, it can be accessed to retrieve information about the path found.- Parameters:
graph
- the graph to be searchedstartVertex
- the vertex at which the path should startendVertex
- the vertex at which the path should end
-
DijkstraShortestPath
public DijkstraShortestPath(Graph<V,E> graph, V startVertex, V endVertex, double radius)
Creates and executes a new DijkstraShortestPath algorithm instance. An instance is only good for a single search; after construction, it can be accessed to retrieve information about the path found.- Parameters:
graph
- the graph to be searchedstartVertex
- the vertex at which the path should startendVertex
- the vertex at which the path should endradius
- limit on path length, or Double.POSITIVE_INFINITY for unbounded search
-
-
Method Detail
-
getPathEdgeList
public java.util.List<E> getPathEdgeList()
Return the edges making up the path found.- Returns:
- List of Edges, or null if no path exists
-
getPath
public GraphPath<V,E> getPath()
Return the path found.- Returns:
- path representation, or null if no path exists
-
getPathLength
public double getPathLength()
Return the length of the path found.- Returns:
- path length, or Double.POSITIVE_INFINITY if no path exists
-
findPathBetween
public static <V,E> java.util.List<E> findPathBetween(Graph<V,E> graph, V startVertex, V endVertex)
Convenience method to find the shortest path via a single static method call. If you need a more advanced search (e.g. limited by radius, or computation of the path length), use the constructor instead.- Parameters:
graph
- the graph to be searchedstartVertex
- the vertex at which the path should startendVertex
- the vertex at which the path should end- Returns:
- List of Edges, or null if no path exists
-
-