好的，由于这个练习，我发布了这个问题：
我们可以修改Dijkstra的算法以通过将最小值更改为最大值来解决单源最长路径问题吗？如果是这样，则证明您的算法正确。如果不是，则提供一个反例。
对于本练习或与Dijkstra算法有关的所有事情， 我假设图中没有负权重 。否则，这没有什么意义，因为即使存在最短路径问题，如果存在负边缘，Dijkstra也无法正常工作。
好吧，我的直觉为我回答了：
是的，我认为可以修改。
我只是
distance[w] > distance[v]+weight
distance[w] < distance[v]+weight
首先，由于上面的帖子，我认为我的答案是错误的。但是我发现上面帖子中的答案可能是错误的。它将 单源最长路径问题 与 最长路径问题 混合在一起。
同样在Bellman-Ford算法的 Wiki中，它正确地表示：
Bellman-Ford算法可计算加权有向图中的单源最短路径。 对于仅具有非负边缘权重的图，更快的Dijkstra算法也解决了该问题 。因此，Bellman-Ford主要用于具有负边缘权重的图形。
所以我认为我的答案是正确的，对吗？Dijkstra确实可以是 “单源 最长路径问题”，我的修改也正确，对吗？
不，我们不能1-或至少不会知道多项式的减少/修改- 最长路径问题是NP- Hard，而dijkstra在多项式时间内运行！
如果我们可以找到对dijsktra的修改来回答多项式时间内的最长路径问题，则可以得出 P=NP
P=NP
如果不是，则提供一个反例。
这是非常糟糕的任务。反例可以提供特定的修改是错误的，而可以进行其他修改就可以了。 事实是，我们不知道最长路径问题在多项式时间内是否可以解决，但一般的假设是-事实并非如此。
关于只是更改放松步骤：
A / \ 1 2 / \ B<--1---C edges are (A,B),(A,C),(C,B)
来自A的dijkstra将首先选择B，然后B永远无法到达-因为它不在的集合中distances。
distances
至少，还必须将“最小堆”更改为“最大堆”，但是它将有一个不同的反例来说明为什么失败。
（1）可能，如果P = NP是可能的，但可能性很小。
