寻找最长路径为＆lt; = X（加权，无向图） [英] FInding the longest path that is <= x (weighted, undirected graph)

问题描述

我想不出任何算法，将发现的最长路径，即小于或等于一些x变量。随着Dijkstra算法我可以轻松地获得最长的路径，但我不知道如果我能在我的问题中使用它。

I can't think of any algorithm that would find the longest path, that is smaller or equal to some x variable. With Dijkstra's algorithm I can easily get longest path, however I'm not sure if I can use it in my problem.

推荐答案

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

Dijkstra's algorithm will give you the shortest path, not the longest one.

查找最长的（简单的）路径是一个NP难。由于您的问题可以退化成最长的路径问题（以X等于所有边权重之和，这是一个上限的最长路径的长度），它也是NP难的。

Finding the longest (simple) path is NP-Hard. Since your problem can be degenerated into the longest path problem (take x equal to the sum of all edge weights, which is an upper bound on the length of the longest path), it is also NP-Hard.

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

You could still use a tree search, but it is not likely to be tractable.

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

If you are considering non-simple paths (nodes can be traversed several times) then it is a different problem. A degenerate case is the knapsack problem, which is NP-Hard as well.

这篇关于寻找最长路径为＆lt; = X（加权，无向图）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！