Public Member Functions | |
| GraphSearch_Dijkstra (Graph graph) | |
| LinkedList< GraphNode > | search (int startID, int targetID) |
| LinkedList< GraphNode > | search (int startID, int targetID, boolean remember) |
| GraphEdge[] | getExaminedEdges () |
| GraphNode[] | getRoute () |
| LinkedList< GraphNode > | search (int startID, int targetID) |
| LinkedList< GraphNode > | search (int startID, int targetID, boolean remember) |
| GraphEdge[] | getExaminedEdges () |
| public< T > T[] | getExaminedEdges (T[] array) |
| GraphNode[] | getRoute () |
| public< T > T[] | getRoute (T[] array) |
Protected Member Functions | |
| double | getCost (GraphNode node) |
Protected Attributes | |
| Graph | graph |
| HashSet< GraphNode > | settledNodes |
| PriorityQueue< GraphNodeCost > | unsettledNodes |
| HashMap< GraphNode, GraphNode > | parent |
| HashMap< GraphNode, Double > | graphCostToNode |
| HashSet< GraphEdge > | examinedEdges |
| LinkedList< GraphNode > | route |
Detailed Description
Dijkstra
Objects of this class are used to search a graph and find a path between two nodes using this algorithm.
Constructor & Destructor Documentation
◆ GraphSearch_Dijkstra()
| pathfinder.GraphSearch_Dijkstra.GraphSearch_Dijkstra | ( | Graph | graph | ) |
Create a search object that uses Dijkstra's algorithm for the given graph.
- Parameters
-
graph the graph to use
Member Function Documentation
◆ getCost()
|
protected |
Used by the search method
- Parameters
-
node
- Returns
◆ getExaminedEdges()
| GraphEdge[] pathfinder.GraphSearch_Dijkstra.getExaminedEdges | ( | ) |
Get all the edges examined during the search.
- Returns
- edges examined or array size 0 if none found
Implements pathfinder.IGraphSearch.
◆ getRoute()
| GraphNode[] pathfinder.GraphSearch_Dijkstra.getRoute | ( | ) |
Get the path found as an array of GraphNode(s) in start->end order
- Returns
- path found or array size 0 if none found
Implements pathfinder.IGraphSearch.
◆ search() [1/2]
| LinkedList< GraphNode > pathfinder.GraphSearch_Dijkstra.search | ( | int | startID, |
| int | targetID | ||
| ) |
Search for a route from node startID and ends at targetID.
This will return a linkedlist of the nodes that make up the route from start to end order.
If either the start or target node does not exist or if a route can't be found the returned list is empty.
- Parameters
-
startID id of the start node targetID id of the target node
- Returns
- the route as a list of nodes
Implements pathfinder.IGraphSearch.
◆ search() [2/2]
| LinkedList< GraphNode > pathfinder.GraphSearch_Dijkstra.search | ( | int | startID, |
| int | targetID, | ||
| boolean | remember | ||
| ) |
Search for a route from node startID and ends at targetID.
This will return a linkedlist of the nodes that make up the route from start to end order.
If either the start or target node does not exist or if a route can't be found the returned list is empty.
- Parameters
-
startID id of the start node targetID id of the target node remember whether to remember the examined edges.
- Returns
- the route as a list of nodes
Implements pathfinder.IGraphSearch.
Member Data Documentation
◆ examinedEdges
|
protected |
Used to remember examined edges
◆ graphCostToNode
|
protected |
Stores the smallest path cost found so far for a given node
◆ parent
Indicates the predecessor node for a given node. This is used to store the shortest path. <node of interest, node where the edge originated>
◆ route
|
protected |
List for routes nodes in order of travel
◆ settledNodes
|
protected |
The settled nodes - the nodes whose shortest distances from the source have been found.
◆ unsettledNodes
|
protected |
The unsettled nodes
The documentation for this class was generated from the following file:
- /Users/peter/git/path-finder-repos/Path Finder/src/pathfinder/GraphSearch_Dijkstra.java
