algorithm - 加权有向图的最大成本和路径算法

Question

对于加权有向图，有哪些算法可以找到从顶点 A 到顶点 K的最大成本和路径？

我在考虑修改后的 Dijkstra，但是在观看和学习这个算法时，我发现它不能用于负权重，也不能用于找到最大成本。

Answer 1

我建议如下：选择最小成本（距离）的任何算法，也适用于负边缘（因此 Dijkstra 不能用于此）。然后使用对每条边的成本求反来运行此算法。例如，您可以使用Bellman-Ford算法。

Answer 2

您可以使用 A*（A 星）算法的修改版本。我说修改，但实际上不会修改。你只需要一个适当的启发式。这是一种寻路算法，您只需要设置启发式方法来选择成本最高的路径。

A* 的工作原理是从某个顶点 V 开始，并将该顶点的所有相邻邻居添加到一个开放列表中。然后，在您的情况下，它会移动到成本最高的节点。先前访问过的节点被移动到一个封闭的列表中。然后将当前节点的所有相邻节点添加到打开列表中。等等等等。

它会找到您的 K，如果您的启发式方法是始终选择成本最高的路径，那么您将获得最大成本路径。

这是应用于 Infinite Mario 的 A*。