graph - Dijkstra 图中的最长路径

Question

我只是想知道：您可以反转图中的所有权重，然后进行 Dijkstra 吗？当我们最小化权重的倒数时，得到的路径会最大化，对吧？因此，通过这种方式，我们可以使用 Dijkstra 获得图中的最长路径！这似乎太容易了，我弄错了吗？请赐教。

Answer 1

通过一个简单的示例图很容易理解。

假设你想从 A 点到 D 点。为了最小化权重的倒数，你会经过 C。但是 A->B->D 更大。

编辑：也许我至少应该包括一些数学。

假设一个正数序列的和是s。

a1 + a2 + a3 + ... + an = s.

倒数的最小值是多少？

1/a1 + 1/a2 + 1/a3 + ... + 1/an

玩这个会给你一些直觉。

Answer 2

这是不可能的，因为longest path problem没有最优子结构问题shortest path。

假设您可以将任何路径视为最长路径（因此它可以有循环），但是如果存在循环并且权重为正，则算法将永远不会结束，因为它始终可以通过循环遍历循环来改进最长路径。

现在假设我们只想将简单路径（没有循环）作为最长路径的候选者。在不失一般性的情况下，考虑以下所有边的权重单一的图：

A------B
|      |
|      |
C------D

并考虑从A到D( A->B->D) 的最长路径。对于具有最佳子结构属性的问题，从A到的最长路径必须B是，A -> B但显然不是因为路径A->C->D->B更长。可以对 fromB到的路径进行类似的论证D。所以我们可以看到为什么这个问题不能用 Dijkstra 算法解决。事实上，这个问题是NP，没有一个合理的时间复杂度解决方案。