我对加权图上的最优算法问题有疑问。我得到了一个带有权重的边缘列表、一个带有保存点的列表、一个开始节点和结束节点以及一个步骤的最大距离。 输出应该是保存点列表，可以从起始节点和结束节点一步访问这些保存点。
我从保存点列表的每个点想到了某种迪杰斯特拉算法。
我不确定这是否是个好主意，因为如果我有很多保存点，我会多次计算很多路径。欢迎任何想法/帮助!
非常感谢您!
最佳答案
你必须要有权重不能为负的条件，否则问题会变得很棘手。否则它只是广度优先搜索，标记每个访问节点的距离。所以你不会重新访问一个节点，因为之前的移动已经以较低的成本更早地访问过它。
您保留所有事件节点的优先级队列，因此您每次都检查成本最低的节点。优先级队列实际上是最难搞定的部分。如果你检查我的二进制图像库的 A* 算法 https://github.com/MalcolmMcLean/binaryimagelibrary你可以在那里拿优先队列。迷宫上的 A* 与图上的最短路径非常相似，但你没有启发式方法，因为你必须有精确的最短路径，而不是每 block 4/8 条边，你有具有任意数量连接的节点.
关于algorithm - 最短路径算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45894925/