Package org.geotools.graph.path
Class DijkstraShortestPathFinder
Object
DijkstraShortestPathFinder
- All Implemented Interfaces:
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
ConstructorsConstructorDescriptionDijkstraShortestPathFinder
(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
Modifier and TypeMethodDescriptionvoid
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
Returns the cost associated with a node calculated during the graph traversal.Returns a path from g to the source.int
visit
(Graphable element, GraphTraversal traversal) Does nothing except signal the traversal to continue.
-
Constructor Details
-
DijkstraShortestPathFinder
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 Details
-
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
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:
-
getCost
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
-
getTraversal
-
visit
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:
-
finish
public void finish()Does nothing.- Specified by:
finish
in interfaceGraphWalker
- See Also:
-