cycle - 通过强连通分量寻找最佳路径

Question

我有一个强连接的有向图，每个节点都有一些价格（正负）。我想找到从节点 A 到节点 B 的最佳（最高分）路径。我的解决方案是某种残酷的力量，因此需要很长时间才能找到该路径。有任何算法或任何想法我该怎么做？

Answer 1

你试过A*算法吗？

这是一种相当流行的寻路算法。算法本身并不难实现，但是网上有很多实现。

Dijkstra 算法是 A* 的一种特殊情况（其中启发式函数 h(x) = 0）。

还有其他算法可以超越它，但它们通常需要图形预处理。如果问题不复杂并且您正在寻找快速解决方案，请尝试一下。

编辑：

对于包含负边的图，有Bellman-Ford算法。但是，检测负循环是以性能为代价的（比 A* 差）。但它仍然可能比您当前使用的要好。

编辑2：

用户@templatetypedef 说贝尔曼-福特算法可能在这里不起作用时是对的。

BF 适用于存在负权重边的图。然而，算法在找到负循环时停止。我相信这是一种有用的行为。在包含负权重循环的图中优化最短路径就像走下彭罗斯楼梯一样。

如果有可能达到“负无限成本”的路径，应该发生什么取决于问题。