图 - 单源最长路径的 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.

我只是

1. 将距离数组初始化为 MININT
2. 更改<代码>距离[w] >distance[v]+weight 到 distance[w] <距离[v]+重量

<小时>

然后我做了一些研究来验证我的答案.我找到了这个帖子:

---

Then I did some research to verify my answer. I found this post:

之间的最长路径源到 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.

也在 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?

推荐答案

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

No, we cannot¹ - 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屋！