algorithm - 寻找 <= x 的最长路径（加权无向图）

Question

我想不出任何可以找到最长路径的算法，即小于或等于某个 x 变量。使用 Dijkstra 的算法，我可以轻松获得最长的路径，但是我不确定是否可以在我的问题中使用它。

Answer 1

Dijkstra 的算法会给你最短的路径，而不是最长的。

寻找最长（简单）路径是 NP-Hard。由于您的问题可以退化为最长路径问题（取 x 等于所有边权重的总和，这是最长路径长度的上限），因此它也是 NP-Hard。

您仍然可以使用树搜索，但它不太可能易于处理。

如果您正在考虑非简单路径（节点可以遍历多次），那么这是一个不同的问题。一个退化的情况是背包问题，它也是 NP-Hard 问题。

Answer 2

您可以使用 DFS 算法来找到最长的路径。如果您搜索，您会发现一些有用的文章，例如Depth First Search & Directed Acyclic Graphs。