Dijkstra是DAG中最长的路径

Question

我试图找出是否有可能使用Dijkstra算法找到有向非循环路径中的最长路径.我知道由于负成本周期,在一般图表中找不到Dijkstra的最长路径是不可能的.但我认为它应该在DAG中起作用.通过谷歌,我发现了很多相互矛盾的消息来源.有人说它在dag中工作,有些人说它不起作用,但我没有找到证明或反例.有人能指出我的证据或反例吗？

Answer 1

我想到了这个问题,我认为一般来说这是不可能的.我想,存在非循环是不够的.

例如:

我们想在这个dag中从a到c.

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

dc的长度为4

广告的长度为1

所有其他人的长度都是2

如果你只用max函数替换min函数,算法将导致abc,但最长的路径是adc.

我发现了两个特殊情况,您可以使用Dijkstra计算最长路径:

1. 图表不仅是非循环的,而且如果你删除了方向,也是非循环的.换句话说:它是一棵树.因为在树中,最长路径也是最短路径.
2. 该图只有负权重.然后你可以使用max而不是min来找到最长的路径.但这只适用于权重确实为负的情况.如果你只是反转正重量它将无法正常工作.

Answer 2

最长距离问题对于任何图（没有DAG）都没有最佳子结构。但是，图G上的任何最长距离问题都等同于变换后的图G'=-G中的最短距离问题，即每个边缘权重的符号都相反。

如果期望变换后的图G'具有负边缘和周期，则使用Bellman-Ford算法查找最短距离。但是，如果保证G仅具有非负权重（即G'为非正权重），那么与Bellman-Ford相比，Dijkstra的算法可能是更好的选择。（请参见图表的 “ Evgeny Kluev”响应-单源最长路径的Dijkstra）如果G是DAG，那么G'也是DAG。对于DAG，我们有更好的算法来查找最短距离，应该选择Dijkstra或Bellman-Ford的算法。

简介：
最长路径问题没有最优的子结构，因此将Dijkstra算法中的最小权重函数修改为仅最大权重函数对图不起作用，无论是否为DAG。我们没有修改任何最短路径算法（很简单），而是对G进行了变换，然后看看哪种最短路径算法在变换后的G上效果最好。

注意

     A-------B
     |       |              assume: edges A-B, B-C, C-A of same weight
     |       |
     +-------C

我们看到MAX_DIS（A，B）= A-> C-> B
对于“ MAX_DIS”为最佳结构，在上述情况下，关系为

    MAX_DIS(A,B) = MAX_DIS(A,C) + MAX_DIS(C,B) should be satisfied.

但这不是我们所看到的，MAX_DIS（A，C​​）= A-> B-> C和MAX_DIS（C，B）= C-> A-> B，因此它提供了一个最长距离问题可能不存在的示例最佳子结构。