带权重限制的最大权重路径问题：是否存在多项式时间解法？

Great question! Let's break this down clearly to understand why this problem still doesn't have a known polynomial-time solution (unless P=NP).

First, a critical clarification: when discussing "maximum weight paths" here, we have to be referring to simple paths (paths with no repeated vertices). If cycles were allowed, the positive edge weights (all ≥1) would let us loop around a cycle infinitely to make the path weight arbitrarily large—making the problem trivial and uninteresting in that scenario.

Here's the core reasoning:

• The classic longest simple path problem (finding the longest path in a general directed graph, measured by number of edges) is a well-established NP-hard problem.
• We can easily reduce this classic problem to your weighted version: take any instance of the longest simple path problem, assign a weight of 1 to every edge (which fits your constraint of weights between 1 and |V|). The length of the longest simple path in the original problem is exactly equal to the maximum weight of a path in this weighted graph.

Since we can reduce an NP-hard problem to your problem in polynomial time, your problem is also NP-hard. This means there's no known polynomial-time algorithm to solve it for general directed graphs—unless the P=NP conjecture is true, which is widely disbelieved by the theoretical computer science community.

A quick caveat: if the graph was a Directed Acyclic Graph (DAG), we could compute the longest path in polynomial time using topological sorting. But your question specifies a general directed graph, so this exception doesn't apply here.

内容的提问来源于stack exchange，提问作者user3443082