I understand how dijkstra algorithm works but I don't know how I should figure out path. How can I get nodes that are on the shortest path?
Dijkstra's algorithm operates in two passes:
- Explore the state space (and assign a total distance value to each node) stop when target is reached
- Browse the generated date to construct the path
You're at step 1: you reached the destination and know there's a path, but heven't extracted it yet, you're missing this second part.
If you only kept track of the 'open' nodes list, and 'closed' nodes list, that is insufficient. You can fix it in two ways:
1. Assign a distance value to each node
Classically, on a grid map, something like
On a Graph, you can store it in a
Map<Node, Double> distanceToGetToNode
More simply, you can expand your Node to store it in a field like
Once you have it, work from the end node backwards, and find its neighbour with the lowest distance value. Store it, iterate until you get to the start node (with distance value 0, obviously).
The full node list is your path (reverse it because it goes end-->start)
Pro: It's quite efficient to store the distance grid if you need to reuse the path from the start point.
Con: It is annoying to find which ancestor has the lowest distance.
2. Remember each node's ancestor
This is much easier. Whenever you uncover a neighbour B to a Node A, assaign A as B's parent: 'b.setParent(a)'
Once Dijstra found the end node, just iterate
end.parent.parent.parent... until you get to your start Node. Reverse it. Job Done.
Pro: It is really easy and efficient to construct the path.
Of course you can (should?) store both the distance and the ancestor in a Node (and when you wanna switch to A-Star, you'll store a heuristic in there too!)