15

我试图找出是否可以使用 Dijkstra 算法来找到有向无环路径中的最长路径。我知道由于负成本周期，不可能在一般图表中找到 Dijkstra 的最长路径。但我认为它应该在 DAG 中工作。通过谷歌，我发现了很多相互矛盾的来源。有人说它在 dag 中有效，有人说它不起作用，但我没有找到证据或反例。有人可以指出我的证据或反例吗？

4

6 回答 6

12

我考虑了这个问题，我认为一般来说这是不可能的。我认为，无环是不够的。

例如：

我们想在这个 dag 中从 a 转到 c。

a - > b - > c
|           /\
v           |
d - - - - -

dc 的长度为 4

广告长度为 1

所有其他人的长度为 2

如果只是将 min 函数替换为 max 函数，算法将导致 abc 但最长的路径是 adc。

我发现了两个可以使用 Dijkstra 计算最长路径的特殊情况：

  1. 该图不仅是有向无环的，而且如果您删除方向，它也是无环的。换句话说：它是一棵树。因为在一棵树中，最长的路径也是最短的路径。
  2. 该图只有负权重。然后你可以使用 max 而不是 min 来找到最长的路径。但这仅在权重确实为负时才有效。如果您只是反转正权重，它将不起作用。
于 2011-11-10T15:28:09.507 回答
8

最长距离问题对于任何图（无论是否有 DAG）都没有最优子结构。然而，图 G 上的任何最长距离问题都等价于变换后的图 G'=-G 中的最短距离问题，即每个边权重的符号是相反的。

如果预期变换后的图 G' 具有负边和负环，则使用 Bellman-Ford 算法来寻找最短距离。然而，如果 G 保证只有非负权重（即 G' 是非正权重），那么 Dijkstra 算法可能是比 Bellman-Ford 更好的选择。（请参阅图表的“Evgeny Kluev”响应 - Dijkstra 的单源最长路径）如果 G 是 DAG，那么 G' 也将是 DAG。对于 DAG，我们有更好的算法来寻找最短距离，应该选择 Dijkstra 或 Bellman-Ford 的算法。

总结：
最长路径问题没有最优子结构，因此将 Dijkstra 算法中的最小权重函数修改为单独的最大权重函数对图不起作用，无论是否为 DAG。我们不是修改任何最短路径算法（以一种简单的方式），而是转换 G，看看哪种最短路径算法在转换后的 G 上效果最好。

笔记

     A-------B
     |       |              assume: edges A-B, B-C, C-A of same weight
     |       |
     +-------C

我们看到 MAX_DIS(A,B)= A->C->B
对于“MAX_DIS”是最优结构，在上述情况下，关系

    MAX_DIS(A,B) = MAX_DIS(A,C) + MAX_DIS(C,B) should be satisfied.

但它不是我们所看到的，MAX_DIS(A,C)=A->B->C 和 MAX_DIS(C,B)= C->A->B 因此它提供了一个最长距离问题可能没有的例子最优子结构。

于 2016-11-28T11:47:44.947 回答
1

应用 Dijkstra 有 3 种可能的方法，其中没有一种会起作用：
1.直接使用“max”操作而不是“min”操作。
2.将所有正权重转换为负数。然后找到最短路径。
3.给一个非常大的正数M。如果一条边的权重是w，现在用Mw代替w。然后找到最短路径。

对于 DAG，关键路径方法将起作用：
1：找到拓扑排序。
2：找到关键路径。
参见 [Horowitz 1995] E. Howowitz、S. Sahni 和 D. Metha，C++ 数据结构基础，计算机科学出版社，纽约，1995

于 2013-03-16T03:35:45.653 回答
1

我建议你修改 Dijkstra 的算法来取边缘权重的倒数。因为图是非循环的，所以算法不会进入死循环，使用负权重来保持优化。更重要的是，现在正权重变为负数，但同样没有周期。即使图形是无向的，这也可以工作，前提是您不允许重新插入访问的节点（即停止两个节点之间的无休止跳转，因为添加负值总是更好）。

于 2014-05-17T22:57:16.780 回答
0

唯一的要求是没有负循环。如果您没有循环，那么您可以通过将负权重中的最高绝对值添加到所有权重来重新映射负数。这样，您将失去负重量，因为所有重量都将等于或大于零。所以总结一下，唯一需要担心的是没有负循环。

于 2011-11-06T14:10:02.040 回答
0

没有足够的声誉来评论@punkyduck 的答案，但我想提一下在 DAG中min替换为max

a ——2——→ b ——2——→ c
│                 ↑
│                 │
1                 4
│                 │
└——————→ d ———————┘

确实有效，因为算法会

  • 首先检查a⇨⇨ab=2, ad=1l(b)=(ab,2), l(d)=(ad,1)
  • 然后检查b，因为我们使用了max⇨⇨abc=2l(c)=(abc,2)
  • 然后检查c，因为abc>ad⇨没有任何反应
  • 最后检查d⇨⇨adc=5更新l(c)=(adc,5)

所以在最后一步adc找到了正确的最长路径。只是为了指出错误。

于 2020-04-08T12:22:55.640 回答