c# - 两个顶点之间的最长路径

Question

我有一个带加权边的有向图(权重都是正数)。

现在，我正在寻找一种高效的算法或代码(特别是 C#)来找到两个给定顶点之间的最长路径。

Answer 1

这完全等同于所有负权重的最短路径算法。为此，您需要验证没有负权重循环(在您的原始情况下可能等同于验证没有正权重循环)。最好的办法是对权重进行加法逆运算并运行 Bellman-Ford，然后对结果进行加法逆运算。