### Documentation / Algorithms / Shortest path

# 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.