问题描述
我想不出任何算法，将发现的最长路径，即小于或等于一些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（加权，无向图）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！