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

最短路径算法

  •  1
  • Timmathy  · 技术社区  · 7 年前

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

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

    提前非常感谢!

    1 回复  |  直到 7 年前
        1
  •  1
  •   Malcolm McLean    7 年前

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

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