org.graphstream.algorithm

## Class Dijkstra

• All Implemented Interfaces:
Algorithm, SpanningTree

```public class Dijkstra
extends AbstractSpanningTree```

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.

This implementation uses internally Fibonacci Heap, a data structure that makes it run faster for big graphs.

### 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 `Dijkstra.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 using different solution access methods.

### Usage

A typical usage of this class involves the following steps:

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.

### Example

``` Graph graph = ...;

// Edge lengths are stored in an attribute called "length"
// The length of a path is the sum of the lengths of its edges
// The algorithm will store its results in attribute called "result"
Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.edge, "result", "length");

// Compute the shortest paths in g from A to all nodes
dijkstra.init(graph);
dijkstra.setSource(graph.getNode("A"));
dijkstra.compute();

// Print the lengths of all the shortest paths
for (Node node : graph)
System.out.printf("%s->%s:%6.2f%n", dijkstra.getSource(), node, dijkstra.getPathLength(node));

// Color in blue all the nodes on the shortest path form A to B
for (Node node : dijkstra.getPathNodes(graph.getNode("B")))

// Color in red all the edges in the shortest path tree
for (Edge edge : dijkstra.getTreeEdges())

// Print the shortest path from A to B
System.out.println(dijkstra.getPath(graph.getNode("B"));

// Build a list containing the nodes in the shortest path from A to B
// Note that nodes are added at the beginning of the list
// because the iterator traverses them in reverse order, from B to A
List <Node> list1 = new ArrayList<Node>();
for (Node node : dijkstra.getPathNodes(graph.getNode("B")))

// A shorter but less efficient way to do the same thing
List<Node> list2 = dijkstra.getPath(graph.getNode("B")).getNodePath();
```
Author:
Stefan Balev
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
`static class ` `Dijkstra.Element`
This enumeration is used to specify how the length of a path is computed
• ### Constructor Summary

Constructors
Constructor and Description
`Dijkstra()`
Constructs an instance in which the length of the path is considered to be the number of edges.
```Dijkstra(Dijkstra.Element element, java.lang.String resultAttribute, java.lang.String lengthAttribute)```
Constructs an instance with the specified parameters.
```Dijkstra(Dijkstra.Element element, java.lang.String resultAttribute, java.lang.String lengthAttribute, java.lang.String flagAttribute, java.lang.Object flagOn, java.lang.Object flagOff)```
Constructs an instance with the specified parameters.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `clear()`
Removes the attributes used to store internal solution data in the nodes of the graph.
`void` `compute()`
Computes the shortest paths from the source node to all nodes in the graph.
`java.lang.String` `defaultResult()`
`java.lang.Iterable<org.graphstream.graph.Path>` `getAllPaths(org.graphstream.graph.Node target)`
An iterable view of of all the shortest paths from the source node to a given target node.
`java.util.stream.Stream<org.graphstream.graph.Path>` `getAllPathsStream(org.graphstream.graph.Node target)`
This iterator traverses all the shortest paths from the source node to a given target node.
`org.graphstream.graph.Edge` `getEdgeFromParent(org.graphstream.graph.Node target)`
Returns the edge between the target node and the previous node in the shortest path from the source to the target.
`org.graphstream.graph.Node` `getParent(org.graphstream.graph.Node target)`
Returns the node preceding the target in the shortest path from the source to the target.
`org.graphstream.graph.Path` `getPath(org.graphstream.graph.Node target)`
Returns the shortest path from the source node to a given target node.
`java.lang.Iterable<org.graphstream.graph.Edge>` `getPathEdges(org.graphstream.graph.Node target)`
An iterable view of the edges on the shortest path from the source node to a given target node.
`java.util.stream.Stream<org.graphstream.graph.Edge>` `getPathEdgesStream(org.graphstream.graph.Node target)`
This iterator traverses the edges on the shortest path from the source node to a given target node.
`double` `getPathLength(org.graphstream.graph.Node target)`
Returns the length of the shortest path from the source node to a given target node.
`java.lang.Iterable<org.graphstream.graph.Node>` `getPathNodes(org.graphstream.graph.Node target)`
An iterable view of the nodes on the shortest path from the source node to a given target node.
`java.util.stream.Stream<org.graphstream.graph.Node>` `getPathNodesStream(org.graphstream.graph.Node target)`
This iterator traverses the nodes on the shortest path from the source node to a given target node.
`<T extends org.graphstream.graph.Node>T` `getSource()`
Dijkstra's algorithm computes shortest paths from a given source node to all nodes in a graph.
`java.util.stream.Stream<org.graphstream.graph.Edge>` `getTreeEdgesStream()`
Dijkstra's algorithm produces a shortest path tree rooted in the source node.
`double` `getTreeLength()`
Dijkstra's algorithm produces a shortest path tree rooted in the source node.
`void` `setSource(org.graphstream.graph.Node source)`
Dijkstra's algorithm computes shortest paths from a given source node to all nodes in a graph.
`void` `setSource(java.lang.String source)`
`void` `setTarget(java.lang.String target)`
• ### Methods inherited from class org.graphstream.algorithm.AbstractSpanningTree

`getFlagAttribute, getFlagOff, getFlagOn, getTreeEdges, init, setFlagAttribute, setFlagOff, setFlagOn`
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### Dijkstra

```public Dijkstra(Dijkstra.Element element,
java.lang.String resultAttribute,
java.lang.String lengthAttribute)```
Constructs an instance with the specified parameters. The edges of the shortest path tree are not tagged.
Parameters:
`element` - Graph elements (edges or/and nodes) used to compute the path lengths. If `null`, the length of the path is computed using edges.
`resultAttribute` - Attribute name used to store internal solution data in the nodes of the graph. If `null`, a unique name is chosen automatically.
`lengthAttribute` - Attribute name used to define individual element lengths. If `null` the length of the elements is considered to be one.
• #### Dijkstra

`public Dijkstra()`
Constructs an instance in which the length of the path is considered to be the number of edges. Unique result attribute is chosen automatically. The edges of the shortest path tree are not tagged.
• #### Dijkstra

```public Dijkstra(Dijkstra.Element element,
java.lang.String resultAttribute,
java.lang.String lengthAttribute,
java.lang.String flagAttribute,
java.lang.Object flagOn,
java.lang.Object flagOff)```
Constructs an instance with the specified parameters.
Parameters:
`element` - Graph elements (edges or/and nodes) used to compute the path lengths. If `null`, the length of the path is computed using edges.
`resultAttribute` - Attribute name used to store internal solution data in the nodes of the graph. If `null`, a unique name is chosen automatically.
`lengthAttribute` - Attribute name used to define individual element lengths. If `null` the length of the elements is considered to be one.
`flagAttribute` - attribute used to set if an edge is in the spanning tree
`flagOn` - value of the flagAttribute if edge is in the spanning tree
`flagOff` - value of the flagAttribute if edge is not in the spanning tree
• ### Method Detail

• #### getSource

`public <T extends org.graphstream.graph.Node> T getSource()`
Dijkstra's algorithm computes shortest paths from a given source node to all nodes in a graph. This method returns the source node.
Returns:
the source node
`setSource(Node)`
• #### setSource

`public void setSource(org.graphstream.graph.Node source)`
Dijkstra's algorithm computes shortest paths from a given source node to all nodes in a graph. This method sets the source node.
Parameters:
`source` - The new source node.
`getSource()`
• #### setSource

`public void setSource(java.lang.String source)`
• #### setTarget

`public void setTarget(java.lang.String target)`
• #### clear

`public void clear()`
Removes the attributes used to store internal solution data in the nodes of the graph. Use this method to free memory. Solution access methods must not be used after calling this method.
Specified by:
`clear` in interface `SpanningTree`
Overrides:
`clear` in class `AbstractSpanningTree`
• #### compute

`public void compute()`
Computes the shortest paths from the source node to all nodes in the graph.
Specified by:
`compute` in interface `Algorithm`
Overrides:
`compute` in class `AbstractSpanningTree`
Throws:
`java.lang.IllegalStateException` - if `AbstractSpanningTree.init(Graph)` or `setSource(Node)` have not been called before or if elements with negative lengths are discovered.
`Algorithm.compute()`
Computational Complexity:
O(m + nlogn) where m is the number of edges and n is the number of nodes in the graph.
• #### getPathLength

`public double getPathLength(org.graphstream.graph.Node target)`
Returns the length of the shortest path from the source node to a given target node.
Parameters:
`target` - A node
Returns:
the length of the shortest path or `Double.POSITIVE_INFINITY` if there is no path from the source to the target
Computational Complexity:
O(1)
• #### getTreeLength

`public double getTreeLength()`
Dijkstra's algorithm produces a shortest path tree rooted in the source node. This method returns the total length of the tree.
Returns:
the length of the shortest path tree
Computational Complexity:
O(n) where n is the number of nodes is the graph.
• #### getEdgeFromParent

`public org.graphstream.graph.Edge getEdgeFromParent(org.graphstream.graph.Node target)`
Returns the edge between the target node and the previous node in the shortest path from the source to the target. This is also the edge connecting the target to its parent in the shortest path tree.
Parameters:
`target` - a node
Returns:
the edge between the target and its predecessor in the shortest path, `null` if there is no path from the source to the target or if the target and the source are the same node.
`getParent(Node)`
Computational Complexity:
O(1)
• #### getParent

`public org.graphstream.graph.Node getParent(org.graphstream.graph.Node target)`
Returns the node preceding the target in the shortest path from the source to the target. This node is the parent of the target in the shortest path tree.
Parameters:
`target` - a node
Returns:
the predecessor of the target in the shortest path, `null` if there is no path from the source to the target or if the target and the source are the same node.
`getEdgeFromParent(Node)`
Computational Complexity:
O(1)
• #### getPathNodesStream

`public java.util.stream.Stream<org.graphstream.graph.Node> getPathNodesStream(org.graphstream.graph.Node target)`
This iterator traverses the nodes on the shortest path from the source node to a given target node. The nodes are traversed in reverse order: the target node first, then its predecessor, ... and finally the source node. If there is no path from the source to the target, no nodes are traversed. This iterator does not support `Iterator.remove()`.
Parameters:
`target` - a node
Returns:
an iterator on the nodes of the shortest path from the source to the target
`getPathNodes(Node)`
Computational Complexity:
Each call of `Iterator.next()` of this iterator takes O(1) time
• #### getPathNodes

`public java.lang.Iterable<org.graphstream.graph.Node> getPathNodes(org.graphstream.graph.Node target)`
An iterable view of the nodes on the shortest path from the source node to a given target node. Uses `getPathNodesStream(Node)`.
Parameters:
`target` - a node
Returns:
an iterable view of the nodes on the shortest path from the source to the target
`getPathNodesStream(Node)`
• #### getPathEdgesStream

`public java.util.stream.Stream<org.graphstream.graph.Edge> getPathEdgesStream(org.graphstream.graph.Node target)`
This iterator traverses the edges on the shortest path from the source node to a given target node. The edges are traversed in reverse order: first the edge between the target and its predecessor, ... and finally the edge between the source end its successor. If there is no path from the source to the target or if he source and the target are the same node, no edges are traversed. This iterator does not support `Iterator.remove()`.
Parameters:
`target` - a node
Returns:
an iterator on the edges of the shortest path from the source to the target
`getPathEdges(Node)`
Computational Complexity:
Each call of `Iterator.next()` of this iterator takes O(1) time
• #### getPathEdges

`public java.lang.Iterable<org.graphstream.graph.Edge> getPathEdges(org.graphstream.graph.Node target)`
An iterable view of the edges on the shortest path from the source node to a given target node. Uses `getPathEdgesStream(Node)`.
Parameters:
`target` - a node
Returns:
an iterable view of the edges on the shortest path from the source to the target
`getPathEdgesStream(Node)`
• #### getAllPathsStream

`public java.util.stream.Stream<org.graphstream.graph.Path> getAllPathsStream(org.graphstream.graph.Node target)`
This iterator traverses all the shortest paths from the source node to a given target node. If there is more than one shortest paths between the source and the target, other solution access methods choose one of them (the one from the shortest path tree). This iterator can be used if one needs to know all the paths. Each call to `Iterator.next()` method of this iterator returns a shortest path in the form of `Path` object. This iterator does not support `Iterator.remove()`.
Parameters:
`target` - a node
Returns:
an iterator on all the shortest paths from the source to the target
`getAllPaths(Node)`
Computational Complexity:
Each call of `Iterator.next()` of this iterator takes O(m) time in the worst case, where m is the number of edges in the graph
• #### getAllPaths

`public java.lang.Iterable<org.graphstream.graph.Path> getAllPaths(org.graphstream.graph.Node target)`
An iterable view of of all the shortest paths from the source node to a given target node. Uses `getAllPathsStream(Node)`
Parameters:
`target` - a node
Returns:
an iterable view of all the shortest paths from the source to the target
`getAllPathsStream(Node)`
• #### getTreeEdgesStream

`public java.util.stream.Stream<org.graphstream.graph.Edge> getTreeEdgesStream()`
Dijkstra's algorithm produces a shortest path tree rooted in the source node. This iterator traverses the edges of this tree. The edges are traversed in no particular order.
Specified by:
`getTreeEdgesStream` in interface `SpanningTree`
Specified by:
`getTreeEdgesStream` in class `AbstractSpanningTree`
Returns:
an iterator on the edges of the shortest path tree
`AbstractSpanningTree.getTreeEdges()`
Computational Complexity:
Each call of `Iterator.next()` of this iterator takes O(1) time
• #### getPath

`public org.graphstream.graph.Path getPath(org.graphstream.graph.Node target)`
Returns the shortest path from the source node to a given target node. If there is no path from the source to the target returns an empty path. This method constructs a `Path` object which consumes heap memory proportional to the number of edges and nodes in the path. When possible, prefer using `getPathNodes(Node)` and `getPathEdges(Node)` which are more memory- and time-efficient.
Parameters:
`target` - a node
Returns:
the shortest path from the source to the target
Computational Complexity:
O(p) where p is the number of the nodes in the path
• #### defaultResult

`public java.lang.String defaultResult()`