如何以最大成本找到路径

Question

我有一个有向图，其顶点有成本。我想在两个顶点之间找到成本最高的路径，但我只找到算法来以最小的代价求解路径。

另外，我正在使用Java。

Answer 1

1. 规格化所有成本，使得最小成本大于0
2. 变化一切代价（1 /费用）。
3. 运行最低成本算法。

生成的路径是原始图上的最大成本路径。

Answer 2

只需修改所用算法的评估函数即可。如果对于最短路径，该函数为较短路径返回更大的值，在这种情况下，您希望为较短路径返回较小的值。