图-Dijkstra用于单源最长路径

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

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

对于本练习或与Dijkstra算法有关的所有事情，

。否则，这没有什么意义，因为即使存在最短路径问题，如果存在负边缘，Dijkstra也无法正常工作。

好吧，我的直觉为我回答了：

是的，我认为可以修改。

我只是

首先，由于上面的帖子，我认为我的答案是错误的。但是我发现上面帖子中的答案可能是错误的。它将与混合在一起。

同样在Bellman-Ford算法的

Wiki中，它正确地表示：

Bellman-Ford算法可计算加权有向图中的单源最短路径。
。因此，Bellman-Ford主要用于具有负边缘权重的图形。

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

不，我们不能1-或至少不会知道多项式的减少/修改-

最长路径问题是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是可能的，但可能性很小。