最短路径算法

我对加权图上的最佳算法问题有疑问。给我一个带有权重的边界列表，一个带有保存点的列表，一个starte和end-node以及一个步骤的最大距离。输出应该是一个保存点列表，可以从开始节点和结束节点一步访问。最短路径算法

我想到了保存点列表中每个点的某种dijkstra算法。

我不确定这是个好主意，因为如果我有很多保存点，我会多次计算很多路径。欢迎每个想法/帮助！

非常感谢您提前！

来源

2017-08-26 Timmathstf

Do dijkstra从开始和结束节点。在遍历图时，要记住你看到的保存点，直到你到达总成本大于步长的节点。 –

哦，这听起来好多了！非常感谢你！ – Timmathstf

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

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

来源

2017-08-26 11:49:55

谢谢，我可以看到相似之处！对不起，我没有说，但重量都是正面的，使它更容易。 – Timmathstf

最短路径算法

回答

相关问题