org.jgrapht.alg.shortestpath

## Class DijkstraShortestPath<V,E>

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

public final class DijkstraShortestPath<V,E>
extends Object
An implementation of Dijkstra's shortest path algorithm using a Fibonacci heap.
Author:
John V. Sichi

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.ShortestPathAlgorithm

ShortestPathAlgorithm.SingleSourcePaths<V,E>
• ### Field Summary

Fields
Modifier and Type Field and Description
protected Graph<V,E> graph
The underlying graph.
• ### Constructor Summary

Constructors
Constructor and Description
DijkstraShortestPath(Graph<V,E> graph)
Constructs a new instance of the algorithm for a given graph.
DijkstraShortestPath(Graph<V,E> graph, double radius)
Constructs a new instance of the algorithm for a given graph.
• ### Method Summary

All Methods
Modifier and Type Method and Description
protected GraphPath<V,E> createEmptyPath(V source, V sink)
Create an empty path.
static <V,E> GraphPath<V,E> findPathBetween(Graph<V,E> graph, V source, V sink)
Find a path between two vertices.
GraphPath<V,E> getPath(V source, V sink)
Get a shortest path from a source vertex to a sink vertex.
ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
Compute all shortest paths starting from a single source vertex.
double getPathWeight(V source, V sink)
Get the weight of the shortest path from a source vertex to a sink vertex.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Field Detail

• #### graph

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

• #### DijkstraShortestPath

public DijkstraShortestPath(Graph<V,E> graph)
Constructs a new instance of the algorithm for a given graph.
Parameters:
graph - the graph
• #### DijkstraShortestPath

public DijkstraShortestPath(Graph<V,E> graph,
double radius)
Constructs a new instance of the algorithm for a given graph.
Parameters:
graph - the graph
radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search
• ### Method Detail

• #### getPath

public GraphPath<V,E> getPath(V source,
V sink)
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 ShortestPathAlgorithm.SingleSourcePaths<V,E> getPaths(V source)
Compute all shortest paths starting from a single source vertex. Note that in the case of Dijkstra's algorithm it is more efficient to compute all single-source shortest paths using this method than repeatedly invoking getPath(Object, Object) for the same source but different sink vertex.
Specified by:
getPaths in interface ShortestPathAlgorithm<V,E>
Parameters:
source - the source vertex
Returns:
the shortest paths
• #### findPathBetween

public static <V,E> GraphPath<V,E> findPathBetween(Graph<V,E> graph,
V source,
V sink)
Find a path between two vertices. For a more advanced search (e.g. limited by radius), use the constructor instead.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the graph to be searched
source - the vertex at which the path should start
sink - the vertex at which the path should end
Returns:
a shortest path, or null if no path exists
• #### getPathWeight

public double getPathWeight(V source,
V sink)
Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.
Specified by:
getPathWeight in interface ShortestPathAlgorithm<V,E>
Parameters:
source - the source vertex
sink - the sink vertex
Returns:
the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY 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