图 - Dijkstra算法的单源最长路径

本文介绍了图 - Dijkstra算法的单源最长路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

好吧，我张贴，因为这项工作的这样一个问题：

Ok, I posted this question because of this exercise:

我们能修改Dijkstra算法来解决，通过改变最小到最大的单一来源的最长路径问题？如果是的话，那就证明你的算法是正确的。如果不是，则提供一个反例。

在本练习或与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]＆GT;距离[V] +重量到距离[W]＆LT;距离[V] +重量

然后我做了一些研究来验证我的答案。我发现这个职位：

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

Longest从DAG中某些节点源之间的路径

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.

此外，在 Bellman-Ford算法的维基，它正确地说，

Also in wiki of Bellman–Ford algorithm, it said correctly :

在Bellman-Ford算法计算单源最短路径的加权有向图。 对于图形只有非负边权重，更快Dijkstra算法也解决了这个问题。因此，贝尔曼 - 福特主要用于图形与下降沿的权重。

所以，我想我的答案是正确的，对不对？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难，而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!

如果我们能找到一个modfication到dijsktra回答在多项式时间最长路径问题，我们可以得到 P = NP

If we can find a modfication to dijsktra to answer longest-path problem in polynomial time, we can derive P=NP

如果不是，则提供一个反

这是非常糟糕的任务。计数器例如可以提供一个具体的修改是错误的，而有可能是不同的变形例即行。
事实是，我们不知道最长的路径问题是solveable在多项式时间或没有，但一般的假设是 - 它不是

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是永远无法到达 - 因为它是出了一套距离

最起码，你将不得不也改变最小堆变成最大堆，却会产生不同的反例失败的原因。

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算法的单源最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！