org.jgrapht.alg.shortestpath

Class DijkstraShortestPath<V,E>

java.lang.Object

org.jgrapht.alg.shortestpath.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 pairing heap by default. A custom heap implementation can by specified during the construction time.

Author:

John V. Sichi

Nested Class Summary

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.
protected static String	GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE Error message for reporting the existence of a negative-weight cycle.
protected static String	GRAPH_MUST_CONTAIN_THE_SINK_VERTEX Error message for reporting that a sink vertex is missing.
protected static String	GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX Error message for reporting that a source vertex is missing.

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.
DijkstraShortestPath(Graph<V,E> graph, double radius, Supplier<org.jheaps.AddressableHeap<Double,Pair<V,E>>> heapSupplier) Constructs a new instance of the algorithm for a given graph.
DijkstraShortestPath(Graph<V,E> graph, Supplier<org.jheaps.AddressableHeap<Double,Pair<V,E>>> heapSupplier) Constructs a new instance of the algorithm for a given graph.

Method Summary

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_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

Error message for reporting the existence of a negative-weight cycle.

See Also:

Constant Field Values

GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

Error message for reporting that a source vertex is missing.

See Also:

Constant Field Values

GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

Error message for reporting that a sink vertex is missing.

See Also:

Constant Field Values

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. The constructed algorithm will use pairing heap as a default heap implementation.

Parameters:

graph - the graph

DijkstraShortestPath

public DijkstraShortestPath(Graph<V,E> graph,
                            double radius)

Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use pairing heap as a default heap implementation.

Parameters:

graph - the graph

radius - limit on path length, or Double.POSITIVE_INFINITY for unbounded search

DijkstraShortestPath

public DijkstraShortestPath(Graph<V,E> graph,
                            Supplier<org.jheaps.AddressableHeap<Double,Pair<V,E>>> heapSupplier)

Constructs a new instance of the algorithm for a given graph. The constructed algorithm will use the heap supplied by the heapSupplier

Parameters:

graph - the graph

heapSupplier - supplier of the preferable heap implementation

DijkstraShortestPath

public DijkstraShortestPath(Graph<V,E> graph,
                            double radius,
                            Supplier<org.jheaps.AddressableHeap<Double,Pair<V,E>>> heapSupplier)

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

heapSupplier - supplier of the preferable heap implementation

Method Detail

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 or using another heap), 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

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

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