无向无权树中遍历必访节点返回起点的最短路径求解及Python实现

首先明确题目给出的无向无权图满足n个节点n-1条边，本质是树结构，任意两个节点之间的最短路径唯一，长度等于两点之间的边数。
这个问题属于树上的旅行商问题（TSP），要求遍历所有必访节点后返回起点，按以下步骤解决即可：

• 距离预处理：因为是无权图，用BFS计算距离比Dijkstra效率更高，你之前考虑的Dijkstra也可使用，但BFS更适配当前场景。我们可以先计算所有节点两两之间的最短距离，若必访节点数量很少，也可以只对起点和所有必访节点执行BFS减少计算量。
• 状态压缩DP：本题场景下必访节点数k一般不超过20，用二进制mask表示已经访问过的必访节点集合即可：
  • 定义dp[mask][i]为已经访问过mask对应的必访节点集合，当前停留在第i个必访节点时的最短路径长度
  • 初始化：dp[1<<i][i] = 节点1到第i个必访节点的距离
  • 状态转移：遍历所有mask，对每个mask里存在的必访节点i，尝试转移到未访问的必访节点j，更新dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j], dp[mask][i] + 必访节点i到必访节点j的距离)
• 结果计算：所有必访节点都访问完（mask等于(1<<k)-1）后，加上当前必访节点回到起点1的距离，取最小值就是最终答案。

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    k = int(data[idx])
    idx += 1
    # 没有必访节点直接返回0
    if k == 0:
        print(0)
        return
    targets = list(map(int, data[idx:idx+k]))
    idx += k
    # 构建邻接表
    adj = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    # BFS预处理所有节点两两最短距离
    dist = [[0]*(n+1) for _ in range(n+1)]
    for start in range(1, n+1):
        q = deque([start])
        visited = [False]*(n+1)
        visited[start] = True
        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    dist[start][v] = dist[start][u] + 1
                    q.append(v)
    
    # 状压DP初始化
    INF = float('inf')
    dp = [[INF]*k for _ in range(1<<k)]
    for i in range(k):
        dp[1<<i][i] = dist[1][targets[i]]
    
    # 状态转移
    for mask in range(1<<k):
        for i in range(k):
            if not (mask & (1<<i)) or dp[mask][i] == INF:
                continue
            for j in range(k):
                if mask & (1<<j):
                    continue
                new_mask = mask | (1<<j)
                dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[targets[i]][targets[j]])
    
    # 计算最终结果
    full_mask = (1<<k) - 1
    ans = INF
    for i in range(k):
        ans = min(ans, dp[full_mask][i] + dist[targets[i]][1])
    print(ans)

if __name__ == "__main__":
    main()

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