DAG 中最长路径的 Dijkstra

Question

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

Answer 1

我想过这个问题，我认为一般来说是不可能的。我认为非循环是不够的。

例如:

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

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

d-c 的长度为 4

a-d 长度为 1

所有其他人的长度为 2

如果你只是用 max 函数替换 min 函数，算法将导致 a-b-c 但最长的路径是 a-d-c。

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

该图不仅是有向无环图，如果去除方向，图也是无环图。换句话说:它是一棵树。因为在树中最长的路径也是最短的路径。

该图只有负权重。然后你可以使用 max 而不是 min 来找到最长的路径。但是这只有在权重真的为负时才有效。如果您只是反转正权重，它将不起作用。