Dijkstra用于DAG中的最长路径 [英] Dijkstra for longest path in a DAG

问题描述

我正在尝试找出是否有可能使用Dijkstra的算法在有向无环路径中找到最长的路径。我知道，由于成本周期为负值，不可能在一般图中找到与Dijkstra最长的路径。我认为它应该在DAG中起作用。通过Google，我发现了许多相互矛盾的来源。有人说它行得通，有人说它行不通，但我没有找到证明或反例。有人可以给我指出一个证明或反例吗？

I am trying to find out if it is possible to use Dijkstra's algorithm to find the longest path in a directed acyclic path. I know that it is not possible to find the longest path with Dijkstra in a general graph, because of negative cost cycles. But it should work in a DAG, I think. Through Google I found a lot of conflicting sources. Some say it works in a dag and some say it does not work, but I didn't find a proof or a counter example. Can someone point me to a proof or a counter example?

推荐答案

我想到了这个问题，但我认为这不可能一般。我认为，无周期性是不够的。

I thought about the problem and I think it is not possible in general. Being acyclic is not enough, I think.

例如：

我们希望在此dag中从a转到c。

We want to go from a to c in this dag.

a - > b - > c
|           /\
v           |
d - - - - - 

dc的长度为4

ad的长度为1

其他所有长度为2

如果您只是替换min函数与max函数，该算法将得出abc，但最长路径为adc。

If you just replace the min function with a max function, the algorithm will lead to a-b-c but the longest path is a-d-c.

我发现了两种特殊情况，您可以使用Dijkstra计算最长路径：

I found two special cases where you can use Dijkstra for calculating the longest path:

1. 图形不仅是有向非有向的，而且如果删除方向也有无向。换句话说：它是一棵树。因为在树上，最长的路径也是最短的路径。


2. 该图仅具有负权重。然后，您可以使用max而不是min来找到最长的路径。但只有权重为负时，此方法才有效。如果您只是反转正重，将无法正常工作。

这篇关于Dijkstra用于DAG中的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！