代码之家 › 专栏 › 技术社区 › Timmathy

最短路径算法

weighted shortest-path graph algorithm

1

Timmathy · 技术社区 · 7 年前

我对加权图上的最优算法问题有疑问。我得到了一个带有权重的边缘列表、一个带有保存点的列表、一个起始和结束节点以及一个步骤的最大距离。输出应该是一个保存点列表,可以从起始节点和结束节点一步访问这些保存点。

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

提前非常感谢!

1 回复 | 直到 7 年前

1

Malcolm McLean 7 年前

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

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