图-狄克斯特拉算法求单源最长路径

Question

12

好的，我发布这个问题是因为这个练习：

我们能通过将最小值改为最大值来修改 Dijkstra 算法以解决单源最长路径问题吗？如果可以，请证明您的算法正确。如果不行，请提供一个反例。

对于这个练习或所有与 Dijkstra 算法相关的事情，我假设图中没有负权重。否则，这就没有多大意义，因为即使对于最短路径问题，如果存在负边缘，Dijkstra 也无法正常工作。

好的，我的直觉告诉我：

是的，我认为它可以被修改。

我只需要：

然后我进行了一些研究以验证我的答案。我找到了这篇文章：

起初我认为我的答案是错误的，因为上面的文章。但我发现可能上面文章中的答案是错误的。它混淆了单源最长路径问题和最长路径问题。

另外，在Bellman-Ford算法的维基中，它正确地说道：

Bellman-Ford算法计算带权有向图中的单源最短路径。对于只有非负边权的图形，更快的Dijkstra算法也可以解决此问题。因此，Bellman-Ford主要用于具有负边权的图形。

所以我认为我的答案是正确的，对吗？Dijkstra确实可以成为单源最长路径问题，而且我的修改也是正确的，对吗？

- Jackson Tale

@Kristo，请你看一下好吗？ - Jackson Tale

3个回答

6

是的，我们可以。你的答案几乎正确，只有一个问题。

你假设没有负权重。在这种情况下，Dijkstra算法无法找到最长路径。

但是，如果你假设只有负权重，你可以很容易地找到最长路径。为了证明正确性，只需取所有权重的绝对值，你就得到了具有正权重的通常Dijkstra算法。

- Evgeny Kluev

1

我认为你的答案有些巧妙。如果我只考虑负权重，那么最长路径就像“所有正权重的最短路径”。我不认为这是练习所要求的。 - Jackson Tale

@JacksonTale，是的，这只是一个技巧。但从练习文本中并不清楚它的含义。否则，amit的答案非常好。 - Evgeny Kluev

谢谢您的回答。我想这个练习的真正意思是针对最长路径问题的。我的错误是加入了这样的假设。 - Jackson Tale

使用Dijkstra算法处理非正权重的想法非常有趣。特别是当我们需要在所有边缘为负或零权重的图G中找到最长路径时，将Dijkstra算法应用于转换后的图G'=（-G）比使用Bellman-Ford算法更明智，以实现更好的运行时间。 - KGhatak

1

它适用于有向无环图，但不适用于循环图。由于路径会返回并且在Dijkstra算法中无法避免这种情况。

- Wolf7176

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

不，我们不能 - 或者至少目前没有已知的多项式约简/修改方法 - 最长路径问题是NP-难题, 而 Dijkstra 算法在多项式时间内运行！

如果我们能找到一种修改 Dijkstra 算法以在多项式时间内回答最长路径问题的方法，我们就可以推导出 P=NP。

如果不行，那么提供一个反例。

这是一个非常糟糕的任务。反例可能会证明某个特定的修改是错误的，而可能有另一种正确的修改方法。事实上，我们不知道最长路径问题是否能够在多项式时间内解决，但一般的假设是它不能。

关于仅更改松弛步骤的问题：

        A
       / \
      1   2
     /     \
    B<--1---C
edges are (A,B),(A,C),(C,B)

从A开始的Dijkstra算法将首先选择B，然后B将永远不可达 - 因为它已经超出了“距离（distances）”集合。至少，还需要将最小堆转换为最大堆，但它将有一个不同的反例说明它失败了。

(1) 可能，如果P=NP的话是可能的，但很不可能。