org.jgrapht.alg

Class BidirectionalDijkstraShortestPath<V,E>

java.lang.Object

org.jgrapht.alg.BidirectionalDijkstraShortestPath<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

public final class BidirectionalDijkstraShortestPath<V,E>
extends Object

A bidirectional version of Dijkstra's algorithm.

See the Wikipedia article for details and references about bidirectional search. This technique does not change the worst-case behavior of the algorithm but reduces, in some cases, the number of visited vertices in practice. This implementation alternatively constructs forward and reverse paths from the source and target vertices respectively.

Since:

July 2016

Author:

Dimitrios Michail

See Also:

DijkstraShortestPath

Constructor Summary

Constructors

Constructor and Description
BidirectionalDijkstraShortestPath(Graph<V,E> graph, V startVertex, V endVertex) Creates the instance and executes the bidirectional Dijkstra shortest path algorithm.
BidirectionalDijkstraShortestPath(Graph<V,E> graph, V startVertex, V endVertex, double radius) Creates the instance and executes the bidirectional Dijkstra shortest path algorithm.

Method Summary

Modifier and Type	Method and Description
static <V,E> 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.
List<E>	getPathEdgeList() Return the edges making up the path.
double	getPathLength() Return the weighted length of the path found.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BidirectionalDijkstraShortestPath

public BidirectionalDijkstraShortestPath(Graph<V,E> graph,
                                         V startVertex,
                                         V endVertex)

Creates the instance and executes the bidirectional Dijkstra shortest path algorithm. An instance is only good for a single search; after construction, it can be accessed to retrieve information about the found path.

Parameters:

graph - the input graph

startVertex - the vertex at which the path should start

endVertex - the vertex at which the path should end

BidirectionalDijkstraShortestPath

public BidirectionalDijkstraShortestPath(Graph<V,E> graph,
                                         V startVertex,
                                         V endVertex,
                                         double radius)

Creates the instance and executes the bidirectional Dijkstra shortest path algorithm. An instance is only good for a single search; after construction, it can be accessed to retrieve information about the found path.

Parameters:

graph - the input graph

startVertex - the vertex at which the path should start

endVertex - the vertex at which the path should end

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

Method Detail

getPathEdgeList

public List<E> getPathEdgeList()

Return the edges making up the path.

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 weighted length of the path found.

Returns:

path length, or Double.POSITIVE_INFINITY if no path exists

findPathBetween

public static <V,E> 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.

Type Parameters:

V - the graph vertex type

E - the graph edge type

Parameters:

graph - the graph to be searched

startVertex - the vertex at which the path should start

endVertex - the vertex at which the path should end

Returns:

List of edges, or null if no path exists