public class AStarIterator extends SourceGraphIterator
// COST(n,n') : the real cost to go from n to n'
OPEN = [Source]
CLOSE = []
while ( |OPEN| > 0 )
n = a node in OPEN with less f
remove n from OPEN
add n to CLOSE
if ( n == target ) {
return // path find
// if n != target
for each node n' that relates to n do
if n' in OPEN
if (g(n) + COST(n,n')) < g(n')
g(n') = g(n) + COST(n,n')
parent(n') = n
else
g(n') = g(n) + COST(n,n')
parent(n') = n
add n' to OPEN
// end while
For more details see http://en.wikipedia.org/wiki/A_starModifier and Type | Class and Description |
---|---|
static class |
AStarIterator.AStarFunctions
Defines the functions needed by A Star.
|
static class |
AStarIterator.AStarNode
Internal data structure used to track node costs, and parent nodes.
|
Constructor and Description |
---|
AStarIterator(Node source,
AStarIterator.AStarFunctions afuncs) |
Modifier and Type | Method and Description |
---|---|
void |
cont(Graphable current,
GraphTraversal traversal)
Makes a step of the A* algorithm.
|
Node |
getParent(Node n) |
protected Iterator<?> |
getRelated(Graphable current) |
void |
init(Graph graph,
GraphTraversal traversal)
Does Nothing.
|
void |
killBranch(Graphable current,
GraphTraversal traversal)
Kills the branch of the traversal
|
Graphable |
next(GraphTraversal traversal)
Returns the next node in the priority queue. if the queue is empty then there is no path from
the source to the destiny in this graph.
|
getSource, setSource
getGraph, getTraversal, getWalker, setTraversal
public AStarIterator(Node source, AStarIterator.AStarFunctions afuncs)
public void init(Graph graph, GraphTraversal traversal)
graph
- The graph being whose components are being iterated over.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)
Copyright © 1996–2023 Geotools. All rights reserved.