Dijkstra's Shortest Path Algorithm
Dijkstra’s algorithm is a greedy algorithm that solves the single-source shortest path problem for a directed graph with non negative edge weights. Check Dijkstra’s algorithm article on the Wikipedia for more details.
This length can be the absolute length of the path (a path with 3 edges has a length of 3), it can also be computed considering other constraints situated on the edges or on the nodes.
Note that Dijkstra’s algorithm only computes with non-negative values.
O(n log(n) + m) with n the number of nodes and m the number of edges.
- E W Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959.
The classical usage of this class takes place in 4 steps.
(i) Definition of a Dijkstra instance with parameters needed for the initialization.
(ii) Initialization of the algorithm with a graph through the
init(Graph) method from the
(iii) Computation of the shortest path tree with the
compute() method from the
(iv) Retrieving of shortest paths for given destinations with the
getShortestPath(Node) method for instance.
The creation of the Dijkstra instance is done with the
Dijkstra(Element, String, String) constructor by giving 3 parameters:
- First, the type of element that is consider for the computing of shortest paths (
- Second, the key string of the attribute used for the weight computation.
- The third parameter is the id of the source node the shortest tree will be constructed for.
The output of this test program should give:
[F, E, D, A]
Shortest Path Value
If you only need to know the value of a shortest path and are not interested in the path itself, then the
getShortestPathValue(Node) method with its given target element is for you.
If you are interested in the length of a path in terms of elements nodes or edges rather than in the path itself or its value, then you can use
getShortestPath(String, Node, Node) is a static method to get shortest paths from a graph already computed with Dijkstra.
This means tha given nodes (source and target) should belong to a
graph that contains attributes with the given
It allows to get rid of Dijkstra instances once computed. Since all the useful information to retrieve a shortest path is stored in the graph, a Dijkstra instance is not necessary. You will use this method if you are computing a lot of instances of Dijkstra in a raw and want to lower the memory consumption.
The 3 following parameters are necessary to this method:
identifier: a unique string used to identify attributes that represent the solution of a Dijkstra computation (a shortest tree rooted in the source node/edge).
source: the source node for what a Dijkstra object as already been initialized.
target: the Target node to be sought in the graph according the given identifier.
All Shortest Paths
It is possible that multiple path in a graph are the shortest ones. Especially if the graph is a grid and the weight is unitary. The
getAllShortestPaths(Node) tries to construct all the possible shortest paths linking the computed source to the given destination.
All Edges involved
getEdgeSetShortestPaths(Node) methods returns the set of edges that are involved in the shortest paths. If Several paths are the shortest paths and some edges belong to several of these paths, then those edge will appear only once. In other words, the return List is a set according to the mathematical definition of a set (no repetition, no order).