如何修改动态规划TSP算法以输出最短路径（附Python代码）

核心修改思路 #

在原有求最短路径长度的记忆化DP基础上，新增一个前驱记录数组prev，用来存储每个状态(当前节点i, 未访问节点集合S)下，选择的最优下一个节点。在计算最短路径长度的同时同步记录前驱信息，最后通过回溯该数组生成完整路径。

修改后的完整代码 #

def tsp_helper(W, i, S, mem, prev):
    if S == 0:
        return 0
    elif mem[i][S] is not None:
        return mem[i][S]
    else:
        mem[i][S] = float('infinity')
        for j in range(len(W)):
            if S & (1 << j) != 0:
                current_cost = W[i][j] + tsp_helper(W, j, S ^ (1 << j), mem, prev)
                if current_cost < mem[i][S]:
                    mem[i][S] = current_cost
                    prev[i][S] = j  # 记录当前状态下的最优下一个节点
        return mem[i][S]

def tsp_memoized(W):
    n = len(W)
    # 初始化记忆化数组和前驱记录数组
    mem = [[None] * (1 << n) for _ in range(n)]
    prev = [[-1] * (1 << n) for _ in range(n)]
    
    min_cost = tsp_helper(W, 0, (1 << n) - 2, mem, prev)
    
    # 回溯生成最短路径
    path = []
    current_node = 0
    current_state = (1 << n) - 2  # 初始状态：除起点0外，所有节点未访问
    path.append(current_node)
    
    while current_state != 0:
        next_node = prev[current_node][current_state]
        path.append(next_node)
        current_state ^= (1 << next_node)  # 标记该节点已访问
        current_node = next_node
    
    # 若需符合TSP"回到起点"的标准要求，取消下方注释
    # path.append(0)
    
    return min_cost, path

# 测试用例
C = [[0,3,6,7],
     [5,0,2,3],
     [6,4,0,2],
     [3,7,5,0]]

min_length, best_path = tsp_memoized(C)
print(f"最短路径长度: {min_length}")
print(f"最短路径: {best_path}")

关键修改点说明 #

1. 前驱数组prev：维度与记忆化数组mem完全一致，每个元素prev[i][S]存储从节点i出发、未访问集合为S时，下一步应前往的最优节点。
2. 同步记录前驱：在更新最短路径长度时，同时将当前最优的下一个节点存入prev数组。
3. 路径回溯：从起点0和初始未访问状态出发，通过prev数组依次推导每一步的节点，直到所有节点都被访问（current_state变为0），最终得到完整路径。
4. 可选的起点回归：如果需要满足TSP“从起点出发并最终返回起点”的标准定义，只需在路径末尾追加起点0即可。

运行结果 #

对于给定的测试矩阵，输出为：

最短路径长度: 7
最短路径: [0, 1, 2, 3]

若开启回到起点的选项，路径变为[0, 1, 2, 3, 0]，总长度为7 + C[3][0] = 7 + 3 = 10。

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