# Dijkstra's Shortest Path Algorithm

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 lengths. Check Dijkstra’s algorithm article on the Wikipedia for more details.

## Complexity

O(n log(n) + m) with n the number of nodes and m the number of edges.

## Reference

• 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 constructors.

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.

## Solutions

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

## Usage

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.