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* [citation needed], and since the difference between their implementation is quite minute, it is often preferable to use the latter. This is especially true in time-intensive software such as games [cite game AI?].
Animated depiction of Dijkstra's algorithm in play. Image from [3].
The algorithm can be summarised into the following steps:
-
- "Open" the beginning node on the graph
-
- Until the total list of nodes is exhausted or the destination is found:
-
- Find the open node with the lowest running 'weight' (e.g. distance)
-
- 2.1. Check the running 'weight' (e.g. distance) of each node neighbouring the currently opened node.
-
- 2.2. Open the node
(THIS NEEDS FINISHING)
- [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]