Package org.geotools.graph.path
Class DijkstraShortestPathFinder
- Object
-
- DijkstraShortestPathFinder
-
- All Implemented Interfaces:
GraphWalker
public class DijkstraShortestPathFinder extends Object implements GraphWalker
Calculates node paths in a graph using Dijkstra's Shortest Path Algorithm. Dijsktras algorithm calculates a shortest path from a specefied node (the source node of the underlying dijkstra iteration) to every other node in the graph.- Author:
- Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
- See Also:
DijsktraIterator
-
-
Constructor Summary
Constructors Constructor Description DijkstraShortestPathFinder(Graph graph, Graphable source, DijkstraIterator.EdgeWeighter weighter)
Constructs a new path finder.DijkstraShortestPathFinder(Graph graph, Graphable source, DijkstraIterator.EdgeWeighter weighter, DijkstraIterator.NodeWeighter nweighter)
Constructs a new path finder.DijkstraShortestPathFinder(Graph graph, DijkstraIterator iterator)
Constructs a new path finder.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
calculate()
Performs the graph traversal and calculates the shortest path from the source node to every other node in the graph.void
finish()
Does nothing.double
getCost(Graphable g)
Returns the cost associated with a node calculated during the graph traversal.DijkstraIterator
getIterator()
Path
getPath(Graphable g)
Returns a path from g to the source.GraphTraversal
getTraversal()
int
visit(Graphable element, GraphTraversal traversal)
Does nothing except signal the traversal to continue.
-
-
-
Constructor Detail
-
DijkstraShortestPathFinder
public DijkstraShortestPathFinder(Graph graph, DijkstraIterator iterator)
Constructs a new path finder.- Parameters:
graph
- The graph to calculate paths for.iterator
- The dijsktra iterator to used to calculate shortest paths.
-
DijkstraShortestPathFinder
public DijkstraShortestPathFinder(Graph graph, Graphable source, DijkstraIterator.EdgeWeighter weighter)
Constructs a new path finder.- Parameters:
graph
- Graph to calculate paths for.source
- Node to calculate paths from.weighter
- Associates weights with edges in the graph.
-
DijkstraShortestPathFinder
public DijkstraShortestPathFinder(Graph graph, Graphable source, DijkstraIterator.EdgeWeighter weighter, DijkstraIterator.NodeWeighter nweighter)
Constructs a new path finder.- Parameters:
graph
- Graph to calculate paths for.source
- Node to calculate paths from.weighter
- Associates weights with edges in the graph.nweighter
- Associates weights with nodes in the graph.
-
-
Method Detail
-
calculate
public void calculate()
Performs the graph traversal and calculates the shortest path from the source node to every other node in the graph.
-
getPath
public Path getPath(Graphable g)
Returns a path from g to the source. If the desired path is the opposite (from the source to g) can be used.- Parameters:
g
- The start node of the path to be calculated.- Returns:
- A path from g to the source.
- See Also:
Walk.riterator()
-
getCost
public double getCost(Graphable g)
Returns the cost associated with a node calculated during the graph traversal.- Parameters:
g
- The node whose cost is desired.- Returns:
- The cost associated with the node.
-
getIterator
public DijkstraIterator getIterator()
-
getTraversal
public GraphTraversal getTraversal()
-
visit
public int visit(Graphable element, GraphTraversal traversal)
Does nothing except signal the traversal to continue.- Specified by:
visit
in interfaceGraphWalker
- Parameters:
element
- The component being visited.traversal
- The traversal controlling the sequence of graph component visits.- Returns:
- GraphTraversal#CONTINUE to signal that the traversal should continue.
GraphTraversal#CONTINUE to signal that the traversal should suspend.
GraphTraversal#KILL_BRANCH to signal that the traversal should kill its current branch.
GraphTraversal#STOP to signal that the traversal should stop. - See Also:
GraphWalker.visit(Graphable, GraphTraversal)
-
finish
public void finish()
Does nothing.- Specified by:
finish
in interfaceGraphWalker
- See Also:
GraphWalker.finish()
-
-