最短路径算法

你必须有一个条件,即权重不能为负,否则问题变得非常棘手。否则,它只是一个广度优先搜索,为每个访问的节点标记距离。所以你不必重新访问一个节点,因为之前的移动已经以较低的成本访问了它。

您保留了所有活动节点的优先级队列,因此每次都要检查成本最低的节点。事实上,优先级队列是最难正确处理的部分。如果你检查我的二进制图像库的A*算法 https://github.com/MalcolmMcLean/binaryimagelibrary 你可以在那里排队。迷宫上的*非常类似于图上的最短路径,但你没有启发式,因为你必须有精确的最短路径,而不是每个图块有4/8条边,你有具有任意数量连接的节点。