不，我们不能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是可能的，但可能性很小。
602392714
清零编程群