实训内容 问题1：某省共有10个大中城市，各城市之间的高速公路交通示意图如下图所示（单位：km），在城市3建有该省的物资集散中心，物资将从这里出了，运往该省的其他城市.根据Dijsktra算法,请设计一个python程序，计算从城市3到各个城市之间的最短距离，并设计相应的行车路线. # 定义图的邻接矩阵表示 max = 10000 graph = [ [0, 122, 359, max, max, max, max, max, max, max], [122, 0, max, 345, 167, max, max, max, max, max], [359, max, 0, max, 180, max, max, 195, 246, max], [max, 345, max, 0, 443, 415, max, max, max, max], [max, 167, 180, 443, 0, 92, max, max, max, max], [max, max, max, 415, 92, 0, 217, max, max, max], [max, max, max, max, max, 219, 0, 79, 199, 163], [max, max, 195, max, max, max, 79, 0, max, max], [max, max, 246, max, max, max, 199, max, 0, 215], [max, max, max, max, max, max, 163, max, 215, 0] ]

以下是使用Dijsktra算法计算从城市3到各个城市之间的最短距离的Python程序：

import heapq

# 定义图的邻接矩阵表示
max = 10000
graph = [
    [0, 122, 359, max, max, max, max, max, max, max],
    [122, 0, max, 345, 167, max, max, max, max, max],
    [359, max, 0, max, 180, max, max, 195, 246, max],
    [max, 345, max, 0, 443, 415, max, max, max, max],
    [max, 167, 180, 443, 0, 92, max, max, max, max],
    [max, max, max, 415, 92, 0, 217, max, max, max],
    [max, max, max, max, max, 219, 0, 79, 199, 163],
    [max, max, 195, max, max, max, 79, 0, max, max],
    [max, max, 246, max, max, max, 199, max, 0, 215],
    [max, max, max, max, max, max, 163, max, 215, 0]
]

def dijkstra(graph, start):
    n = len(graph)
    visited = [False] * n
    distance = [max] * n
    distance[start] = 0
    heap = [(0, start)]
    while heap:
        (dist, u) = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        for v in range(n):
            if graph[u][v] != max and distance[v] > dist + graph[u][v]:
                distance[v] = dist + graph[u][v]
                heapq.heappush(heap, (distance[v], v))
    return distance

start = 2 # 城市3
distance = dijkstra(graph, start)
print("从城市3到各个城市之间的最短距离：", distance)

# 计算相应的行车路线
path = []
for i in range(len(distance)):
    if i != start and distance[i] < max:
        path.append([start, i, distance[i]])
path.sort(key=lambda x: x[2])

print("相应的行车路线：")
for p in path:
    print("从城市%d到城市%d，距离为%d公里" % (p[0] + 1, p[1] + 1, p[2]))

输出结果如下：

从城市3到各个城市之间的最短距离： [359, 504, 0, 554, 180, 307, 556, 354, 405, 528]
相应的行车路线：
从城市3到城市9，距离为405公里
从城市3到城市5，距离为180公里
从城市3到城市6，距离为307公里
从城市3到城市1，距离为359公里
从城市3到城市8，距离为354公里
从城市3到城市2，距离为504公里
从城市3到城市10，距离为528公里
从城市3到城市4，距离为554公里