单源最长路径的图-Dijkstra

Question

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

我们能否修改Dijkstra的算法，通过变极小为极大来解决单源最长路问题？如果是，那么证明你的算法是正确的。如果没有，那么提供一个反例。

1. 将距离数组初始化为minint
2. 将距离[w]>距离[v]+重量更改为距离[w]<距离[v]+重量

然后我做了一些研究来验证我的答案。我发现了这个帖子：

从源到DAG中某些节点之间的最长路径

Answer 1

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

如果我们能在多项式时间内找到dijsktra的一个模化来回答最长路径问题，我们可以导出P=np

如果没有，那么提供一个反例。

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

关于只是改变放松步骤：

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

来自A的dijkstra将首先选择B，然后B永远无法到达--因为它不在距离集之外。

（1）很可能，如果p=np，可能是可能的，但可能性很小。