带权重约束的最大顶点访问路径求解方案及相关问题问询

我已经通过Floyd-Warshall算法计算出加权邻接矩阵对应的任意两点间最短路径矩阵，给定一个固定权重上限，目标是找到一条总权重不超过该上限、且访问顶点数量最多的路径。

我考虑了三种思路：

• 生成所有顶点排列，但这会带来指数级时间复杂度，想问是否可行？
• 采用动态规划，将子问题定义为「约束权重上限下，从节点i到j访问的最大节点数」；
• 将问题转化为以边为变量的线性规划问题，疑惑该问题是否等价于肾交换问题？

另外还有个疑问：如果确认图中不存在负环，是不是最终的最优路径中不会包含环？

附我实现的Floyd-Warshall函数：

def floyd_warshall(G):
    n = len(G)

    # run a modified Bellman-Ford's algorithm on `G`
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # if better path is found, relax
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]
    return G

1. 生成所有排列的可行性 #

完全不可行。当顶点数n超过10时，排列数就突破360万，n=15时更是达到万亿级别，指数级复杂度会直接让计算无法完成，只适用于n≤8的极小规模场景，没有实用价值。

2. 动态规划思路的合理性 #

这是可行且值得深挖的方向，建议优化状态定义：

• 定义状态dp[mask][u]：表示访问过的顶点集合为mask（用二进制位标记，第k位为1代表访问过顶点k），当前位于顶点u时，路径的最小总权重。
• 目标：找到所有满足dp[mask][u] ≤ 权重上限的mask中，二进制位为1的数量最多的那个。

这种定义的优势在于，我们只保留到达「顶点集合+当前顶点」的最小权重，这样能尽可能预留权重余量去访问更多顶点。状态转移逻辑为：
遍历每个mask和其中包含的顶点u，再遍历所有未被访问的顶点v，更新dp[mask | (1<<v)][v] = min(dp[mask | (1<<v)][v], dp[mask][u] + dist[u][v])，其中dist是你已经算出的最短路径矩阵。

该思路的时间复杂度为O(n²×2ⁿ)，n≤16时还能正常运行，n=20左右会因内存和计算量问题变得吃力，但比全排列方案实用得多。

3. 与肾交换问题的等价性 #

不等价。肾交换问题核心是寻找最大匹配的环/链集合，属于匹配问题范畴；而你的问题是寻找单条路径，要求总权重不超上限且顶点数最多，属于带约束的最长顶点数路径问题，两者的问题模型、目标函数完全不同，无法直接套用肾交换的解法。

4. 无负环时最优路径是否含环？ #

是的，最优路径一定不含环。原因很直接：如果路径包含环，由于没有负环，这个环的总权重≥0。去掉该环后，路径总权重不会增加，且顶点数要么不变（环中顶点已在路径其他部分出现），要么减少——但关键是，原路径总权重≤上限的话，去环后的路径总权重也≤上限，甚至可能有更多余量添加其他顶点。因此最优路径不可能包含环，一旦有环，我们总能通过去环得到更优或等价的路径。

关于你的Floyd-Warshall实现 #

注意代码里的注释写的是"modified Bellman-Ford"，这是错误的，Floyd-Warshall是基于动态规划的算法，和Bellman-Ford核心逻辑不同。另外，初始邻接矩阵需要正确初始化：顶点自身到自身的权重设为0，不可达的顶点对权重设为无穷大（比如float('inf')），否则算法可能出现计算错误。

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