Dijkstra’s algorithm computes the shortest paths from a given node called
source to all the other nodes in a graph. It produces a shortest path tree
rooted in the source. This algorithm works only for nonnegative
Check Dijkstra’s algorithm article on the Wikipedia for more details.
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.
Length of a path
Traditionally the length of a path is defined as the sum of the lengths of
its edges. This implementation allows to take into account also the “lengths”
of the nodes. This is done by a parameter of type Element passed in
The lengths of individual elements (edges or/and nodes) are defined using
another constructor parameter called lengthAttribute. If this
parameter is null, the elements are considered to have unit lengths.
In other words, the length of a path is the number of its edges or/and nodes.
If the parameter is not null, the elements are supposed to have a numeric
attribute named lengthAttribute used to store their lengths.
Internal solution data is stored in attributes of the nodes of the underlying
graph. The name of this attribute is another constructor parameter called
resultAttribute. This name must be specified in order to avoid
conflicts with existing attributes, but also to distinguish between solutions
produced by different instances of this class working on the same graph (for
example when computing shortest paths from two different sources. If not
specified, a unique name is chosen automatically based on the hash code of
the Dijkstra instance. The attributes store opaque internal objects and must
not be accessed, modified or deleted. The only way to retrieve the solution
is to use the following solution access methods:
getPathLength(Node) returns the length of the shortest path from the source to a given node
getParent(Node) and getEdgeFromParent(Node) are used to get the previous node or edge in the shortest path from the source to a given node
getPathEdges(Node), getPathEdgesIterator(Node), getPathNodes(Node) and getPathNodesIterator(Node) are used to iterate over the shortest paths computed by the algorithm
getTreeEdges(), getTreeEdgesIterator() and getTreeLength() are used to access the shortest path tree computed by the algorithm
getAllPathsIterator(Node) enumerates all the shortest paths from the source to a given node
A typical usage of this class involves the following steps:
Instantiation using one of the constructors with appropriate parameters
Initialization of the algorithm using init(Graph)
Setting the source node using setSource(Node)
Computation of the shortest paths using compute()
Retrieving the solution using different solution access methods
Cleaning up using clear()
Note that if the graph changes after the call of compute() the
computed solution is no longer valid. In this case the behavior of the
different solution access methods is undefined.