Dijkstra's Algorithm
Between the two points,
Consider each node for weight,
And find short path
Dijkstra's algorithm is a graph-traversal algorithm often used for pathfinding. It was first described by Dijkstra in 1959 [1] and formed the basis for the A* pathfinding algorithm [2].
The algorithm is effective when finding the shortest path to go to another place so that the final path isn't considered too harmful. However, it lacks the computational optimisation introduced by A*, and since the workload of their implementation is similar, it is often preferable to use the latter [4]. This is especially true in time-intensive software such as games.
Animated depiction of Dijkstra's algorithm in play. Image from [3].
- [1] E. W. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math., vol. 1, pp. 269–271, Dec. 1959. Available: http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf [Accessed: 14-Feb-2019]
- [2] M. Nosrati, R. Karimi, and H. A. Hasanvand, "Investigation of the * ( star ) search algorithms : Characteristics , methods and approaches," 2002. Available: https://pdfs.semanticscholar.org/831f/f239ba77b2a8eaed473ffbfa22d61b7f5d19.pdf [Accessed: 14-Feb-2019]
- [3] T. Abiy et al, "Dijkstra's Shortest Path Algorithm", unknown date. [Online]. Available: https://brilliant.org/wiki/dijkstras-short-path-finder/ [Accessed: 14-Feb-2019]
- [4] A. Patel, "Introduction to A*", unknown date. [Online]. Available: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html [Accessed: 15-Feb-2019]