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`
• ### 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`
• ### 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,
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