| org.geotools.graph.traverse.basic.SourceGraphIterator
 org.geotools.graph.traverse.standard.DijkstraIterator
All known Subclasses: org.geotools.graph.traverse.standard.DirectedDijkstraIterator,
| DijkstraIterator | | public class DijkstraIterator extends SourceGraphIterator (Code) | | Iterates over the nodes of a graph in pattern using Dijkstra's
Shortest Path Algorithm. A Dijkstra iteration returns nodes
in an order of increasing cost relative to a specified node
(the source node of the iteration).
In a Dijsktra iteration, a weight is associated with each edge
and a cost with each node. The iteration operates by maintaining
two sets of nodes. The first the set of nodes whose final cost is known, and
the second is the set of nodes whose final cost is unknown.
Initially, every node except for the source node has a cost of infinity, and
resides in the unkown set. The source node has a cost of zero, and is
is a member of the known set.
The iteration operatates as follows:
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 iteration
The following is an illustration of the algorithm. Edge weights are labelled
in blue and the final node costs are labelled in red.
The nodes are returned in order of increasing cost which yields the sequence
A,C,B,D,E,F,G,H,I.
author:
Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net |
| Inner Class :public static interface EdgeWeighter | |
| Inner Class :protected static class DijkstraNode | |
| Constructor Summary | |
| public | DijkstraIterator(EdgeWeighter weighter)
Constructs a new Dijkstra iterator which uses the specided EdgeWeighter. |
| DijkstraIterator | | public DijkstraIterator(EdgeWeighter weighter)(Code) | | Constructs a new Dijkstra iterator which uses the specided EdgeWeighter.
Parameters:
weighter - Calculates weights for edges in the graph being iteratedover. |
| getCost | | public double getCost(Graphable component)(Code) | | Returns the internal cost of a node which has been calculated by the
iterator.
Parameters:
component - The component whose cost to return. The cost associated with the component. |
| getParent | | public Graphable getParent(Graphable component)(Code) | | Returns the last node in the known set to update the node. The iteration
operates by nodes in the known set updating the cost of nodes in the
unknown set. Each time an update occurs, the known node is set as the
parent of the unkown node.
Parameters:
component - The node whose parent to return (child) The parent, or null if the method is supplied the source of the iteration. |
| next | | public Graphable next(GraphTraversal traversal)(Code) | | Returns the next node in the priority queue. If the next node coming out
of the queue has infinite cost, then the node is not adjacent to any nodes
in the set of nodes with known costs. This situation will end the traversal
every other node will also have infinite cost. This usally is the result of
a disconnected graph.
See Also: org.geotools.graph.traverse.GraphIterator.next
See Also: |
|
|