图 - 单源最长路径的 Dijkstra [英] graph - Dijkstra for The Single-Source Longest Path
问题描述
好的,我发布这个问题是因为这个练习:
Ok, I posted this question because of this exercise:
我们可以修改 Dijkstra 算法,通过将最小值变为最大值来解决单源最长路径问题吗?如果是这样,那么证明你的算法是正确的.如果不是,请提供一个反例.
Can we modify Dijkstra’s algorithm to solve the single-source longest path problem by changing minimum to maximum? If so, then prove your algorithm correct. If not, then provide a counterexample.
对于本练习或与 Dijkstra 算法相关的所有内容,我假设图中没有负权重.否则,它没有多大意义,因为即使是最短路径问题,如果存在负边缘,Dijkstra 也无法正常工作.
For this exercise or all things related to Dijkstra's algorithm, I assume there are no negative weights in the graph. Otherwise, it makes not much sense, as even for shortest path problem, Dijkstra can't work properly if negative edge exists.
好的,我的直觉为我解答了:
Ok, my intuition answered it for me:
是的,我认为可以修改.
Yes, I think it can be modified.
我只是
- 将距离数组初始化为 MININT
- 更改<代码>距离[w] >distance[v]+weight 到
distance[w] <距离[v]+重量
<小时>
然后我做了一些研究来验证我的答案.我找到了这个帖子:
Then I did some research to verify my answer. I found this post:
首先我认为我的回答是错误的,因为上面的帖子.但是我发现上面帖子中的答案可能是错误的.它混淆了单源最长路径问题和最长路径问题.
First I thought my answer was wrong because of the post above. But I found that maybe the answer in the post above is wrong. It mixed up The Single-Source Longest Path Problem with The Longest Path Problem.
也在 Bellman–Ford 算法 的 wiki 中,它说正确:
Also in wiki of Bellman–Ford algorithm, it said correctly :
Bellman-Ford 算法计算加权有向图中的单源最短路径.对于只有非负边权重的图,更快的 Dijkstra 算法也解决了这个问题.因此,Bellman-Ford 主要用于具有负边权重的图.
The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph. For graphs with only non-negative edge weights, the faster Dijkstra's algorithm also solves the problem. Thus, Bellman–Ford is used primarily for graphs with negative edge weights.
所以我认为我的答案是正确的,对吗?Dijkstra 真的可以成为单一来源最长路径问题,我的修改也是正确的,对吧?
So I think my answer is correct, right? Dijkstra can really be The Single-Source Longest Path Problem and my modifications are also correct, right?
推荐答案
不,我们不能1 - 或者至少,没有多项式减少/修改是已知的 - 最长路径问题 是NP-Hard>,而 dijkstra 在多项式时间内运行!
No, we cannot1 - or at the very least, no polynomial reduction/modification is known - longest path problem is NP-Hard, while dijkstra runs in polynomial time!
如果我们可以找到对 dijsktra 的修改以在多项式时间内回答最长路径问题,我们可以推导出 P=NP
If we can find a modfication to dijsktra to answer longest-path problem in polynomial time, we can derive P=NP
如果不是,请提供反例.
If not, then provide a counterexample.
这是非常糟糕的任务.反例可以提供一个特定的修改是错误的,而可以有一个不同的修改是可以的.
事实是我们不知道最长路径问题是否可以在多项式时间内解决,但一般假设是 - 不是.
This is very bad task. The counter example can provide a specific modification is wrong, while there could be a different modification that is OK.
The truth is we do not know if longest-path problem is solveable in polynomial time or not, but the general assumption is - it is not.
关于只是改变松弛步骤:
regarding just changing the relaxation step:
A
/
1 2
/
B<--1---C
edges are (A,B),(A,C),(C,B)
来自 A 的 dijkstra 将首先选择 B,然后 B 永远无法到达 - 因为它超出了 distances
的集合.
dijkstra from A will first pick B, and then B is never reachable - because it is out of the set of distances
.
至少,您还必须将最小堆更改为最大堆,但它会具有不同的反例,为什么它会失败.
At the very least, one will have also to change min heap into max heap, but it will have a different counter-example why it fails.
(1) 可能,如果 P=NP 有可能,但可能性很小.
(1) probably, maybe if P=NP it is possible, but it is very unlikely.
这篇关于图 - 单源最长路径的 Dijkstra的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!