求解约束最长路径问题的算法

Question

I 是一个矩阵，表示任意两个节点之间的最短路径，我使用 Bellman Ford 算法从加权邻接矩阵计算得出。此外，我有一个恒定的最大重量。我的目标是找到最大化访问顶点数的路径，同时强制最终路径总权重小于或等于权重限制。一种选择是生成所有排列，但这将是指数时间，不是吗？

另一个想法是应用动态规划，子问题定义为从节点 i 到节点 j 的最大节点数受制于约束。最后，我想将其简化为变量等于边的线性规划问题。那么，是否等同于换肾问题呢？在我检查没有负循环之后，这是否意味着最终最优路径中将有no循环？如果我能澄清问题的任何部分，请告诉我。

我用以下函数创建最短路径矩阵：

def bellman_ford(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