从源s到目标f中的有向循环图中找到最长的路径。假设不存在正重循环

Question

我必须在从源s到目标f的有向循环图中找到最长的路径。假设即使不存在正重循环，也存在0或负重的循环，也没有正重循环。有人可以建议在这种情况下找到最长途径的算法。如果可能的话，请引用来源。

谢谢

Answer 1

我不确定这是否会起作用（需要检查），但是...您可以做类似的事情：

让 min = min weight on the graph.
max = max weight on the graph.
设置所有边缘的新权重= wNew(e) = max - (wOld(e)-min).

现在有负wight，权重是相反的（意味着如果 w(e1) 比大 w(e2) 现在较小）。

如果我们现在搜索最短的路径怎么办？

Answer 2

只需否定边缘的重量并运行最短的路径算法（例如，贝尔曼福音）即可。

零重量周期可能是一个问题。您需要通过选择最短的路线（长度而不是重量）来打破路线。一种方法是使您的体重成为一对（ - （原始权重），1），成对添加它们，然后进行词典订购。

也可以看看 两个顶点之间的最长路径

Answer 3

如果您获得了DCG，则可以在到达目标之前永远循环，这将是“最长的路径”。在这种情况下，问题是不完整的，并且根据细节的不同，该算法可能看起来有所不同。

这听起来像是作业。