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.
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.
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.
A typical usage of this class involves the following steps:
AbstractSpanningTree.init(Graph)
compute()
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.
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"))) node.addAttribute("ui.style", "fill-color: blue;"); // Color in red all the edges in the shortest path tree for (Edge edge : dijkstra.getTreeEdges()) edge.addAttribute("ui.style", "fill-color: red;"); // 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"))) list1.add(0, node); // A shorter but less efficient way to do the same thing List<Node> list2 = dijkstra.getPath(graph.getNode("B")).getNodePath();
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 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,
String resultAttribute,
String lengthAttribute)
Constructs an instance with the specified parameters.
|
Dijkstra(Dijkstra.Element element,
String resultAttribute,
String lengthAttribute,
String flagAttribute,
Object flagOn,
Object flagOff)
Constructs an instance with the specified parameters.
|
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.
|
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.
|
Iterator<org.graphstream.graph.Path> |
getAllPathsIterator(org.graphstream.graph.Node target)
This iterator traverses all the shortest paths from the source
node to a given target node.
|
<T extends 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.
|
<T extends 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.
|
<T extends 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.
|
<T extends org.graphstream.graph.Edge> |
getPathEdgesIterator(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.
|
<T extends 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.
|
<T extends org.graphstream.graph.Node> |
getPathNodesIterator(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> |
getSource()
Dijkstra's algorithm computes shortest paths from a given source node to
all nodes in a graph.
|
<T extends org.graphstream.graph.Edge> |
getTreeEdgesIterator()
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.
|
getFlagAttribute, getFlagOff, getFlagOn, getTreeEdges, init, setFlagAttribute, setFlagOff, setFlagOn
public Dijkstra(Dijkstra.Element element, String resultAttribute, String lengthAttribute)
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.public Dijkstra()
public Dijkstra(Dijkstra.Element element, String resultAttribute, String lengthAttribute, String flagAttribute, Object flagOn, Object flagOff)
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 treeflagOn
- value of the flagAttribute if edge is in the spanning
treeflagOff
- value of the flagAttribute if edge is not in the
spanning treepublic <T extends org.graphstream.graph.Node> T getSource()
setSource(Node)
public void setSource(org.graphstream.graph.Node source)
source
- The new source node.getSource()
public void clear()
clear
in interface SpanningTree
clear
in class AbstractSpanningTree
public void compute()
compute
in interface Algorithm
compute
in class AbstractSpanningTree
IllegalStateException
- if AbstractSpanningTree.init(Graph)
or setSource(Node)
have not
been called before or if elements with negative lengths are
discovered.Algorithm.compute()
public double getPathLength(org.graphstream.graph.Node target)
target
- A nodeDouble.POSITIVE_INFINITY
if there is no path
from the source to the targetpublic double getTreeLength()
public <T extends org.graphstream.graph.Edge> T getEdgeFromParent(org.graphstream.graph.Node target)
target
- a nodenull
if there is no path from the source to the
target or if the target and the source are the same node.getParent(Node)
public <T extends org.graphstream.graph.Node> T getParent(org.graphstream.graph.Node target)
target
- a nodenull
if there is no path from the source to the target or if the
target and the source are the same node.getEdgeFromParent(Node)
public <T extends org.graphstream.graph.Node> Iterator<T> getPathNodesIterator(org.graphstream.graph.Node target)
Iterator.remove()
.target
- a nodegetPathNodes(Node)
Iterator.next()
of this
iterator takes O(1) timepublic <T extends org.graphstream.graph.Node> Iterable<T> getPathNodes(org.graphstream.graph.Node target)
getPathNodesIterator(Node)
.target
- a nodegetPathNodesIterator(Node)
public <T extends org.graphstream.graph.Edge> Iterator<T> getPathEdgesIterator(org.graphstream.graph.Node target)
Iterator.remove()
.target
- a nodegetPathEdges(Node)
Iterator.next()
of this
iterator takes O(1) timepublic <T extends org.graphstream.graph.Edge> Iterable<T> getPathEdges(org.graphstream.graph.Node target)
getPathEdgesIterator(Node)
.target
- a nodegetPathEdgesIterator(Node)
public Iterator<org.graphstream.graph.Path> getAllPathsIterator(org.graphstream.graph.Node target)
Iterator.next()
method of this iterator returns a
shortest path in the form of Path
object.
This iterator does not support Iterator.remove()
.target
- a nodegetAllPaths(Node)
Iterator.next()
of this
iterator takes O(m) time in the worst case, where
m is the number of edges in the graphpublic Iterable<org.graphstream.graph.Path> getAllPaths(org.graphstream.graph.Node target)
getAllPathsIterator(Node)
target
- a nodegetAllPathsIterator(Node)
public <T extends org.graphstream.graph.Edge> Iterator<T> getTreeEdgesIterator()
getTreeEdgesIterator
in interface SpanningTree
getTreeEdgesIterator
in class AbstractSpanningTree
AbstractSpanningTree.getTreeEdges()
Iterator.next()
of this
iterator takes O(1) timepublic org.graphstream.graph.Path getPath(org.graphstream.graph.Node target)
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.target
- a nodeCopyright © 2015. All rights reserved.