我有一个有权重的有向图（所有权重均为正数）。
现在，我正在寻找一种高效的算法或代码（特别是C#），以找到两个给定顶点之间的最长路径。
现在，我正在寻找一种高效的算法或代码（特别是C#），以找到两个给定顶点之间的最长路径。
4个回答
7
这与一个具有所有负权重的最短路径算法完全相同。为了做到这一点，您需要验证是否存在负权重环（在您的原始情况下，这可能等价于验证是否存在正权重环）。最好的方法是取权重的加法逆元并运行Bellman-Ford算法，然后取结果的加法逆元。
- David Berger
3
David Berger的回答是正确的，除非您指的是一条简单路径，在这种情况下，Bellman-Ford算法将无法给出最长路径。由于您说权重为正，当图形具有循环（可从源到达）时，最长路径不存在，除非您指的是简单路径。最长简单路径问题是NP完全问题。请参见Wikipedia。
因此，假设您指的是有向无环图（DAG）。在线性时间内，您可以计算从起始顶点s到每个顶点v的最长路径，前提是您知道从s-> *u到每个u的最长路径，其中u-> v直接。这很容易 - 您可以在有向图上进行深度优先搜索，并按访问它们的相反顺序计算顶点的最长路径。您还可以使用3色标记（已打开但未完成的顶点为灰色）在DFS期间检测回边。再次参见Wikipedia以获取更多信息。在DAG上查找最长/最短路径有时称为维特比算法（尽管它是假定特定类型的DAG而给出的）。我会首先尝试线性时间动态规划解决方案。如果存在循环，则Bellman-Ford也无法解决您的问题。
- Jonathan Graehl
3
如果循环不可达，则最长路径可以存在循环中。此外，如果有任何负权重循环是可达的，Bellman-Ford算法可以返回负无穷大。因此，即使没有明确假设图是无环的，这仍然是一个合理的问题。也许这就是为什么您链接的第一篇维基百科文章推荐使用Bellman-Ford算法的原因。 - David Berger
当你准备进行拓扑排序时，可以使用深度优先搜索来检测源节点可达的子图是否存在环。 - Jonathan Graehl
使用Bellman-Ford算法求最长路径的唯一原因是：1）存在可达的环路
2）但所有这些环路的权重都为0或负数（在权重反转之前）。 - Jonathan Graehl
0
如果有人需要的话，我分享一下我的经验。我曾经花了很长时间寻找解决方案，但最终找到了QuickGraph。我用它来解决一个问题，即查找符合某个规则的最长路径。虽然我在得到第一个结果后采用了一些暴力方法，但这并不是非常优雅的解决方案。以下是我的具体做法。
为了获得最长路径，您可以使用算法来查找长度为-1的最短路径。然后，为了找到后续的最长路径，我开始从该最长路径中删除边缘，以查看是否能够获得“更好”的（基于问题条件）最长路径。- nadasurf
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接