修改Python图遍历代码 实现两点间时间最短路径查询

原代码默认实现了两个节点s、d间所有简单路径的打印功能。已知邻接矩阵adjacency_matrix中位置(i,j)的取值为节点i到节点j的通行时间，需要对代码做如下调整：

• 取消运行时直接打印所有路径的逻辑
• 遍历过程中存储全部可达路径，以及每条路径对应的通行总耗时
• 计算完成后输出总耗时最短的路径

• 给图类新增邻接矩阵（权重矩阵）属性，方便查询任意边的通行时间
• 改造原路径遍历的递归函数：递归过程中同步累计当前路径的总通行时间，到达目标节点时，将当前路径的副本和对应总耗时存入结果集合，避免后续路径回溯修改列表影响已存结果
• 所有路径遍历完成后，遍历结果集合筛选出总耗时最小的条目输出即可

from collections import defaultdict


class Graph:
    def __init__(self, vertices, weight_matrix):
        self.V = vertices
        self.graph = defaultdict(list)
        # 存储边权重（通行时间）
        self.weight_matrix = weight_matrix

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def collectAllPathsUtil(self, u, d, visited, path, current_total_time, all_paths):
        visited[u] = True
        path.append(u)

        if u == d:
            # 到达终点，存储路径副本和总耗时
            all_paths.append((path.copy(), current_total_time))
        else:
            for i in self.graph[u]:
                if not visited[i]:
                    # 累加当前边的通行时间后递归
                    edge_time = self.weight_matrix[u][i]
                    self.collectAllPathsUtil(i, d, visited, path, current_total_time + edge_time, all_paths)

        # 回溯
        path.pop()
        visited[u] = False

    def findShortestPath(self, s, d):
        visited = [False] * self.V
        path = []
        all_paths = []
        self.collectAllPathsUtil(s, d, visited, path, 0, all_paths)
        
        if not all_paths:
            print(f"节点{s}到节点{d}无可达路径")
            return
        # 按总耗时排序取最短
        shortest_path, min_time = min(all_paths, key=lambda x: x[1])
        print(f"节点{s}到节点{d}的最短路径为：{shortest_path}，总通行耗时：{min_time}")
        # 如需查看所有路径可放开下方注释
        # print("所有可达路径及对应耗时：")
        # for p, t in all_paths:
        #     print(f"路径：{p}，耗时：{t}")


n = int(input())

adjacency_matrix = []
for i in range(n):
    row = [0]*n
    adjacency_matrix.append(row)

for i in range(len(adjacency_matrix)):
    for j in range(len(adjacency_matrix[0])):
        adjacency_matrix[i][j] = int(input())

s = int(input())
d = int(input())

pos = [(count1, count2) for count1, lst in enumerate(adjacency_matrix) for count2, num in enumerate(lst) if num != 0]

# 初始化图时传入权重矩阵
g = Graph(n, adjacency_matrix)

for i in pos:
    g.addEdge(*i)

g.findShortestPath(s, d)

• 图类初始化时新增权重矩阵入参，直接复用输入的邻接矩阵查询通行时间，不需要额外维护边到权重的映射结构，减少冗余代码
• 递归函数新增当前路径总耗时、结果存储列表两个参数，到达终点时存储的是路径的副本（path.copy()），避免回溯时pop操作修改已存入结果的路径数据
• 路径收集完成后直接用Python内置min函数按总耗时维度取最小值，不需要手动写循环比较，逻辑更简洁
• 新增无可达路径的边界判断，避免空结果调用min时报错

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