Revision history [back]

Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning.

I have to disagree with @Ben, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route.

The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal.

A great way to understand these two algorithms is to look at the wikipedia pages for A* and Dijkstra's and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly.

Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning.

I have to disagree with @Ben, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route.

The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal.

A great way to understand these two algorithms is to look at the wikipedia pages for A* and Dijkstra's and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly.

Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning.

I have to disagree with @Ben, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route.

The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal.

A great way to understand these two algorithms is to look at the wikipedia pages for A* and Dijkstra's and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly.

EDIT:

The "The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path.