algorithm - 图 - 单源最长路径的 Dijkstra

Question

好的，由于这个练习，我发布了这个问题：

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

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

好的，我的直觉为我回答了这个问题：

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

我只是

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

首先，由于上面的帖子，我认为我的答案是错误的。但是我发现上面帖子中的答案可能是错误的。它将单源最长路径问题与最长路径问题混为一谈。

同样在Bellman-Ford algorithm的 wiki 中，它正确地说：

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

所以我认为我的答案是正确的，对吧？Dijkstra 真的可以是单源最长路径问题，我的修改也是正确的，对吧？

score 10 · Accepted Answer

不，我们不能¹ - 或者至少，没有多项式减少/修改是已知的 -最长路径问题是NP-Hard，而 dijkstra 在多项式时间内运行！

如果我们可以找到对 dijsktra 的修改以在多项式时间内回答最长路径问题，我们可以推导出P=NP

如果不是，请提供一个反例。

这是一个非常糟糕的任务。反例可以提供一个特定的修改是错误的，而可能有一个不同的修改是好的。
事实是我们不知道最长路径问题是否可以在多项式时间内解决，但一般假设是 - 它不是。

关于仅仅改变松弛步骤：

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

来自 A 的 dijkstra 将首先选择 B，然后 B 永远无法到达 - 因为它不在distances.

至少，还必须将最小堆更改为最大堆，但它会有一个不同的反例为什么它会失败。

(1) 可能，如果 P=NP 有可能，但可能性很小。

score 6 · Accepted Answer

我们可以。你的答案几乎是正确的。除了一件事。

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

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

score 1 · Accepted Answer

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

3 回答 3