public class DijkstraIterator extends SourceGraphIterator
sn = source node of iteration N = set of all nodes K = set of nodes with known cost = {sn} U = set of nodes with unknown cost = N  K cost(sn) = 0 for each node $un in U cost(un) = infinity while(U > 0) for each node n in K find a node un in U that relates to n if cost(n) + weight(n,un) < cost(un) cost(un) = cost(n) + weight(n,un) ln = node with least cost in U remove ln from U add ln to K return ln as next node in iterationThe following is an illustration of the algorithm. Edge weights are labelled in blue and the final node costs are labelled in red.
Modifier and Type  Class and Description 

protected static class 
DijkstraIterator.DijkstraNode
Internal data structure used to track node costs, and parent nodes.

static interface 
DijkstraIterator.EdgeWeighter
Supplies a weight for each edge in the graph to be used by the iteration when calculating
node costs.

static interface 
DijkstraIterator.NodeWeighter
Supplies a weight for each pair of adjacent edges.

Modifier and Type  Field and Description 

protected HashMap<Graphable,DijkstraIterator.DijkstraNode> 
nodemap
map of graph node to internal Dijkstra node *

protected DijkstraIterator.NodeWeighter 
nweighter
provides weights for nodes in the graph *

protected PriorityQueue<DijkstraIterator.DijkstraNode> 
queue
priority queue to manage active nodes *

protected DijkstraIterator.EdgeWeighter 
weighter
provides weights for edges in the graph *

Constructor and Description 

DijkstraIterator(DijkstraIterator.EdgeWeighter weighter)
Constructs a new Dijkstra iterator which uses the specified EdgeWeighter.

DijkstraIterator(DijkstraIterator.EdgeWeighter weighter,
DijkstraIterator.NodeWeighter nweighter)
Constructs a new Dijkstra iterator which uses the specified EdgeWeighter and NodeWeighter

Modifier and Type  Method and Description 

void 
cont(Graphable current,
GraphTraversal traversal)
Looks for adjacent nodes to the current node which are in the adjacent node and updates
costs.

double 
getCost(Graphable component)
Returns the internal cost of a node which has been calculated by the iterator.

Graphable 
getParent(Graphable component)
Returns the last node in the known set to update the node.

protected PriorityQueue 
getQueue() 
protected Iterator<? extends Graphable> 
getRelated(Graphable current) 
void 
init(Graph graph,
GraphTraversal traversal)
Builds internal priority queue to manage node costs.

void 
killBranch(Graphable current,
GraphTraversal traversal)
Kills the branch of the traversal by not updating the cost of any adjacent nodes.

Graphable 
next(GraphTraversal traversal)
Returns the next node in the priority queue.

getSource, setSource
getGraph, getTraversal, getWalker, setTraversal
protected DijkstraIterator.EdgeWeighter weighter
protected DijkstraIterator.NodeWeighter nweighter
protected PriorityQueue<DijkstraIterator.DijkstraNode> queue
protected HashMap<Graphable,DijkstraIterator.DijkstraNode> nodemap
public DijkstraIterator(DijkstraIterator.EdgeWeighter weighter)
weighter
 Calculates weights for edges in the graph being iterated over.public DijkstraIterator(DijkstraIterator.EdgeWeighter weighter, DijkstraIterator.NodeWeighter nweighter)
weighter
 Calculates weights for edges in the graph being iterated over.nweighter
 Calculates weights for nodes in the graph being iterated over.public void init(Graph graph, GraphTraversal traversal)
graph
 The graph being whose components are being iterated over.org.geotools.graph.traverse.GraphIterator#init(Graph)
public Graphable next(GraphTraversal traversal)
org.geotools.graph.traverse.GraphIterator#next()
public void cont(Graphable current, GraphTraversal traversal)
current
 The current component of the traversal.org.geotools.graph.traverse.GraphIterator#cont(Graphable)
public void killBranch(Graphable current, GraphTraversal traversal)
current
 The current component of the traversal.org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
public double getCost(Graphable component)
component
 The component whose cost to return.public Graphable getParent(Graphable component)
component
 The node whose parent to return (child)protected PriorityQueue getQueue()
Copyright © 1996–2023 Geotools. All rights reserved.