图 - Dijkstra为单源最长路径 [英] graph - Dijkstra for The Single-Source Longest Path
问题描述
我们可以修改Dijkstra的算法来解决单源最长路径问题通过将最小值改为最大值？如果是这样，那么证明你的算法是正确的。如果没有，则提供一个反例。
对于本练习或与Dijkstra算法相关的所有内容，我认为图中没有负权重。否则，这不是很有意义，即使是最短路径问题，如果存在负边缘，Dijkstra就无法正常工作。
好的，我的直觉回答了我：
是的，我认为可以修改。
我只是
- 将距离数组初始化为MININT
- 更改
distance [w]> distance [v] + weighttodistance [w]距离[v] +重量
然后我做了一些研究来验证我的答案。我发现这篇文章：
首先我以为我的答案是错误的因为上面的帖子。但是我发现上面的帖子也许是错误的。它使用最长路径问题混合单源最长路径问题。
同样在 Bellman-Ford算法，它正确地说：
Bellman-Ford算法计算加权有向图中的单源最短路径。 对于只有非负边缘权重的图形，更快的Dijkstra算法也可以解决问题。因此，Bellman-Ford主要用于具有负边缘权重的图形。
所以我认为我的答案是对的，对吧？
Dijkstra真的可以单源最长路径问题和我的修改也是正确的，对吗？
不，我们不能 1 - 或至少没有多项式缩减/修改已知 - 最长路径问题是 NP-Hard ，而dijkstra运行在多项式时间！ p>
如果我们可以找到对dijsktra的修改来回答多项式时间中的最长路径问题，我们可以导出 P = NP
如果没有，请提供一个反例。
这是非常糟糕的任务。计数器示例可以提供具体的修改是错误的，而可能有不同的修改是可行的。
事实是，我们不知道最长路径问题是否可以在多项式时间内解决，但一般的假设是 - 不是。
< hr>
只要改变放松步骤：
A
/ （A，B），（A，C），（C，B，B），B $ ）
dijkstra从A将首先选择B，然后B永远不可达 - 因为它是距离的集合。
至少，还要将最小堆更改为最大堆，但是它会有一个不同的反例，为什么它失败。
（1）可能，如果P = NP是可能的，但不太可能。
Ok, I posted this question because of this exercise:
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.
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.
I just
- initialise distance array to MININT
- change
distance[w] > distance[v]+weighttodistance[w] < distance[v]+weight
Then I did some research to verify my answer. I found this post:
Longest path between from a source to certain nodes in a DAG
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.
Also in wiki of Bellman–Ford algorithm, it said correctly :
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.
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?
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!
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)
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) probably, maybe if P=NP it is possible, but it is very unlikely.
这篇关于图 - Dijkstra为单源最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
