Skip to main content
Commonmark migration
Source Link

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

##1. Assign a distance value to each node
ClassicallyClassically, 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

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

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

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

Source Link
MrBrushy
  • 431
  • 4
  • 8

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