官术网_书友最值得收藏!

Dijkstra's algorithm

While perhaps not quite as popular as A* Pathfinding (which we will cover next), it's crucial to understand Dijkstra's algorithm, as it lays the foundation for other similar approaches to finding the shortest path between two nodes in a graph. The algorithm was published by Edsger W. Dijkstra in 1959. Dijkstra was a computer scientist, and though he may be best known for his namesake algorithm, he also had a hand in developing other important computing concepts, such as the semaphoreIt might be fair to say Dijkstra probably didn't have StarCraft in mind when developing his algorithm, but the concepts translate beautifully to game AI programming and remain relevant to this day.

So what does the algorithm actually do? In a nutshell, it computes the shortest path between two nodes along a graph by assigning a value to each connected node based on distance. The starting node is given a value of zero. As the algorithm traverses through a list of connected nodes that have not been visited, it calculates the distance to it and assigns the value to that node. If the node had already been assigned a value in a prior iteration of the loop, it keeps the smallest value. The algorithm then selects the connected node with the smallest distance value, and marks the previously selected node as visited, so it will no longer be considered. The process repeats until all nodes have been visited. With this information, you can then calculate the shortest path.

Need help wrapping your head around Dijkstra's algorithm? The University of San Francisco has created a handy visualization tool:  ;https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html.

While Dijkstra's algorithm is perfectly capable, variants of it have been developed that can solve the problem more efficiently. A* is one such algorithm, and it's one of the most widely used pathfinding algorithms in games, due to its speed advantage over Dijkstra's original version.

主站蜘蛛池模板: 雷波县| 精河县| 大田县| 泰安市| 喀喇| 涿鹿县| 红原县| 嘉定区| 卫辉市| 保康县| 贞丰县| 祁东县| 五常市| 霍城县| 阜阳市| 西盟| 潜江市| 鄂温| 乐清市| 汶上县| 茌平县| 筠连县| 陇西县| 平顺县| 奉新县| 肥城市| 辽中县| 宜昌市| 北安市| 土默特右旗| 泸定县| 铁岭县| 贵德县| 金溪县| 八宿县| 六盘水市| 冕宁县| 沁源县| 汉寿县| 盐城市| 道真|