logo标签列表

在有向无环图中求最长路径的Dijkstra算法

dijkstralongest-path
17

我想知道是否可以使用Dijkstra算法在有向无环图中找到最长路径。我知道在一般的图中，由于存在负权重环，使用Dijkstra算法是无法找到最长路径的。但在DAG中应该可以使用，我认为。通过谷歌搜索我发现了很多互相矛盾的信息。有些人说它适用于DAG，而有些人则说它不适用，但我没有找到证据或反例。请问有人能给我提供一个证明或反例吗？

看起来这个方法最长路径问题好像是有效的，但你不太确定？ - yosukesabai
@yosukesabai，您所指的算法并不是Dijkstra算法。 - punkyduck
7个回答
16

我思考了这个问题，我认为一般情况下是不可能的。我认为仅仅是无环并不足够。

例如：

我们想要在这个有向无环图中从a到c。

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

d-c长度为4

a-d长度为1

其他路径的长度均为2

如果你只是将最小函数替换为最大函数，该算法会导致a-b-c成为最长路径，但实际上最长路径是a-d-c。

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

  1. 图不仅是有向无环的，而且如果去掉方向后也是无环的。换句话说：它是一棵树。因为在树中最长路径也是最短路径。
  2. 图仅具有负权值。然后你可以用最大值代替最小值来找到最长路径。但这仅适用于权重确实为负数的情况。如果您仅颠倒正权，则不起作用。
实际上对于（2），您不能有负权重，否则就像是试图寻找最大值（反转对比）一样。您需要找到至少等于最大权重的值，然后对于每个权重：weight = max_weight - weight。然后正常的 Dijkstra 算法将返回您的最长路径。只需执行 path_length*max_weight - dist 即可获得该距离。 - Wernight
你能解释一下这段代码吗？“如果你只是用max函数替换min函数，那么算法会导致a-b-c，但最长路径是a-d-c。”首先从队列中提取节点a，更新其相邻节点，然后提取节点b，再提取c，因为c的距离值为2，大于b的距离值，然后提取d，由于c已经被访问过，所以d不会更新c的距离值。 - Ohhh
@哦，我认为“如果你只是用max函数替换min函数，算法将导致a-b-c，但最长路径是a-d-c。”的意思是通常情况下，你会有一个优先队列，其顶部是最小值，即[(d,1),(b,2)] -> [(b,2),(c,4)]...然而，一旦你使用Dijkstra完成了顶点的遍历，你就将其标记为“已访问”，并在其余的运行中忽略它。这很不幸地是Dijkstra在将优先队列改为取最大值时失败的原因。你得到的结果是，在访问d之前，你先访问了c，即a-b-c与a-d-c的区别。 - StyleZ
8

最长距离问题在任何图形中都没有最优子结构，无论是DAG还是非DAG。然而，在图形G上的任何最长距离问题都等同于在转换后的图形G'中寻找最短距离问题，即每个边权重的符号被反转。

如果预计转换后的图形G'具有负边和循环，则使用Bellman-Ford算法查找最短距离。然而，如果保证G仅具有非负权重（即G'具有非正权重），则Dijkstra算法可能比Bellman-Ford更好的选择。（请参见“Evgeny Kluev”关于单源最长路径的图形-Dijkstra的回答）如果G是DAG，则G'也将是DAG。对于DAG，我们有更好的算法来查找最短距离，并且应该选择它而不是Dijkstra或Bellman-Ford。

摘要：
最长路径问题没有最优子结构，因此仅将Dijkstra算法中的最小权重函数修改为最大权重函数并不能适用于图形，无论是有向无环图还是不是。我们不是以一种琐碎的方式修改任何最短路径算法，而是转换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，因此它提供了一个例子，表明最长距离问题可能没有最优子结构。

1
我认为你的评论中有一个小错误，Djikstra算法不允许在只有负权重的图中找到最短路径，而Evgeny Kluev所说的是它可以通过在具有相反边（将是正数）的图中搜索最短路径来查找只有负权重的图中的最长路径，使用Djikstra算法。 - Thomas
1
答案是肯定的，这是可能的。
Dijkstra算法可以在图中找到最短路径。所以，如果你想修改这个算法来查找图中的最长路径，那么你只需要将边权重乘以“-1”。通过这种改变，最短路径实际上将变成最长路径。
如果你想提取结果，只需将结果乘以“-1”。
以下是一个例子：
using System;
using System.Collections.Generic;
using System.Linq;

namespace Longest_Path
{
public static class Program
{
    public static void Main(string[] args)
    {
        var nodesCount = int.Parse(Console.ReadLine());
        var edgesCount = int.Parse(Console.ReadLine());

        var graph = new List<Edge>[nodesCount + 1];

        var comesFrom = new int[nodesCount + 1];
        var nodesTime = new double[nodesCount + 1];
        for (int i = 0; i <= nodesCount; i++)
        {
            comesFrom[i] = -1;
            nodesTime[i] = double.PositiveInfinity;
        }

        for (int i = 0; i < edgesCount; i++)
        {
            var input = Console.ReadLine().Split();

            var from = int.Parse(input[0]);
            var to = int.Parse(input[1]);
            var weight = double.Parse(input[2]);

            var edge = new Edge(from, to, weight * -1);

            if (graph[from] == null)
            {
                graph[from] = new List<Edge>();
            }

            if (graph[to] == null)
            {
                graph[to] = new List<Edge>();
            }

            graph[from].Add(edge);
        }

        var source = int.Parse(Console.ReadLine());
        var destination = int.Parse(Console.ReadLine());

        nodesTime[source] = 0;

        var priorityQueue = new Queue<int>();
        priorityQueue.Enqueue(source);

        while (priorityQueue.Any())
        {
            var fastestNode = priorityQueue.Dequeue();

            foreach (var child in graph[fastestNode])
            {
                if (!priorityQueue.Contains(child.to))
                {
                    priorityQueue.Enqueue(child.to);
                }

                var currentTime = nodesTime[child.from] + child.weight;
                if (currentTime < nodesTime[child.to])
                {
                    nodesTime[child.to] = currentTime;
                    comesFrom[child.to] = child.from;
                }
            }

            priorityQueue = new Queue<int>(priorityQueue.OrderBy(x => nodesTime[x]));
        }

        Console.WriteLine(nodesTime[destination] * -1);

        var path = new Stack<int>();
        path.Push(destination);
        var currentNode = destination;

        while (comesFrom[currentNode] != -1)
        {
            currentNode = comesFrom[currentNode];
            path.Push(currentNode);
        }

        Console.WriteLine(string.Join(' ', path));
    }
}

public class Edge
{
    public readonly int from;
    public readonly int to;
    public readonly double weight;
    public Edge(int firstNode, int secondNode, double weight)
    {
        this.from = firstNode;
        this.to = secondNode;
        this.weight = weight;
    }
}

}

1
有三种可能的方法可以应用Dijkstra算法，但是这些方法都不可行：
1.直接使用“max”操作而非“min”操作。
2.将所有正权重转换为负数。然后找到最短路径。
3.给定一个非常大的正数M。如果一条边的权重为w，则现在用M-w来替换w。然后找到最短路径。
对于DAG，关键路径方法可行：
1.找到拓扑排序。
2.找到关键路径。
参见[Horowitz 1995] E. Howowitz, S. Sahni和D. Metha，《C++数据结构基础》，计算机科学出版社，纽约，1995年。
1

我建议您修改Dijkstra算法，以考虑边权值的倒数。因为图是无环的，算法不会进入无限循环，并使用负权重来保持优化。此外，现在正的权值变成了负的，但是同样也没有环。即使图是无向的，只要禁止重新插入已访问的节点（即停止两个节点之间的无限跳动，因为添加负值始终会更好），这也将起作用。

0

声望不足，无法评论@punkyduck的答案，但我想提到在DAG中用max替换min

a ——2——→ b ——2——→ c
│                 ↑
│                 │
1                 4
│                 │
└——————→ d ———————┘

实际上是有效的，因为算法将

  • 首先检查 a ⇨ ab=2, ad=1 ⇨ l(b)=(ab,2), l(d)=(ad,1)
  • 然后检查 b，因为我们使用了 max ⇨ abc=2 ⇨ l(c)=(abc,2)
  • 然后检查 c，因为 abc>ad ⇨ 什么也没发生
  • 最后检查 d ⇨ adc=5 ⇨ 更新 l(c)=(adc,5)

因此，在最后一步找到了正确的最长路径 adc。只是指出错误。

1
它不起作用。如果您使用Dijkstra算法，该算法将无法将c的成本更新为5。 - Nabin Kafle
0
唯一的要求是没有负循环。如果没有循环，那么您可以通过将负权重的最高绝对值添加到所有权重中来重新映射负权重。这样，您将失去负权重，因为所有权重都将等于或大于零。因此，总结起来，唯一需要担心的就是没有负循环。
1
这将扭曲路径的长度，因为负循环意味着对于可以通过该循环到达的任何节点，距离为负无穷大，而之后每个距离都是非负的。此外，路径中的边数将支配其长度，当边可以具有权重时，这显然不是意图。 - G. Bach
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接