两个顶点之间的最长路径
我有一个带加权边的有向图（权重都是正数）。
现在，我正在寻找一种有效的算法或代码（特别是C＃）来找到两个给定顶点之间的最长路径。
这完全等同于具有所有负权重的最短路径算法。 要做到这一点，你需要validation没有负重量循环（在你的原始情况下可能相当于validation没有正重量循环）。 最好的办法是采用权重的加法逆并运行Bellman-Ford，然后取结果的加法逆。
David Berger的回答是正确的，除非你的意思是一条简单的路径，每个顶点最多只能出现一次，在这种情况下，Bellman-Ford不会给出最长的路径。 由于您说权重是正数，因此当图形具有循环（可从源到达）时，不可能存在最长路径，除非您的意思是简单路径。 最长的简单路径问题是NP完全。 见维基百科 。
因此，我们假设您的意思是有向无环图（DAG）。 在线性时间内，您可以计算从起始顶点到每个顶点v的最长路径，假设您知道s – > * u的最长路径，对于每个u，其中u-> v直接。 这很简单 – 您可以在有向图上进行深度优先搜索，并以与访问它们相反的顺序计算顶点的最长路径。 您还可以使用3色标记检测整个DFS的后边缘（已打开但未完成的顶点为灰色）。 有关更多信息，请再次查看Wikipedia 。 DAG上的最长/最短路径发现有时被称为维特比算法（即使假设特定类型的DAG给出它）。
我首先尝试线性时间动态编程解决方案。 如果你确实有周期，那么Bellman-Ford无论如何也无法解决你的问题。
请参阅QuickGraph项目，因为它提供了实现图形的.NET数据结构，还提供了对这些数据结构进行操作的算法。 我确定您要查找的算法是在库中实现的。
以防万一它可以帮助任何人，因为我一直在寻找这个但是找不到它，我使用QuickGraph解决了一个问题，我必须找到符合某个规则的最长路径。 它不是很优雅，因为一旦我得到第一个结果我就做了一点蛮力，但现在是。
要获得最长的路径，您可以使用算法来查找长度为lenghts = -1的最短路径。 然后找到后续最长的路径，我开始从那个最长的路径中删除边缘，看看我是否设法得到一个“更好”（基于问题的条件）最长的路径。