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

Question

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

谢谢

score 2 · Accepted Answer

只需否定您的边缘权重并运行最短路径算法（例如，Bellman-Ford）。

零重量循环可能是一个问题。您需要通过选择最短的路径（长度，而不是重量）来打破路径上的关系。一种方法是使您的权重成为一对（-（原始权重），1），将它们成对添加，并进行字典排序。

score 0 · Accepted Answer

如果您有 DCG，则可以在到达目标之前永远循环，这将是“最长的路径”。在这种情况下，问题是不完整的，算法可能会根据具体情况而有所不同。

这听起来像家庭作业。

score 0 · Accepted Answer

我不确定这是否可行（需要检查）但是......你可以做类似的事情：

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

现在有负权重，权重是相反的顺序（意思是如果w(e1)比w(e2)现在更小）。

如果我们现在搜索最短路径会怎样？

3 回答 3