0
\$\begingroup\$

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ Just so I understand that right: You know how the djikstra algorithm works but you don't knoe how to find the shortest path? That's contradictory... \$\endgroup\$ – LukeG Sep 1 '16 at 18:41
  • \$\begingroup\$ It finds the shortest path but I don't know how to "remember" nodes that player should go on to get to the target \$\endgroup\$ – Arek Żyłkowski Sep 1 '16 at 18:45
  • 2
    \$\begingroup\$ Keep them in a vector? \$\endgroup\$ – Vaillancourt Sep 1 '16 at 18:46
  • \$\begingroup\$ But how can code determine which node is good way to destination. I mean there are couple of nodes with the same value( tentative distance) but not all of them lead to destination. \$\endgroup\$ – Arek Żyłkowski Sep 1 '16 at 19:08
  • \$\begingroup\$ when you update a node distance from origin, you should also set a parent to it, to find the complete path, you just start from the end and take parent each time until you reach the origin point \$\endgroup\$ – Guiroux Sep 1 '16 at 20:14
1
\$\begingroup\$

Dijkstra's algorithm operates in two passes:

  1. Explore the state space (and assign a total distance value to each node) stop when target is reached
  2. 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 double[][] distanceToGetHere
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 node.setTotalDistance(double dist)
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.
Con: ?

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!)

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.