在从上海（S）到天津（T）的公路网中，货车司机企图找到一条最短路线，图中A1，和A2 ,……表示货车经停的城市，路线边的数字表示距离（单位：百公里）。 （1）若货车要从上海（S）到天津（T）如何选择行驶路线可以使得距离最短？ （2）求解通过所有城市到达目的地的最短距离？python代码的实现

下面是使用 Dijkstra 算法求解的 Python 代码：

import heapq

# 定义图的邻接矩阵
graph = [[0, 580, 0, 0, 0, 0, 0, 0, 0], 
         [580, 0, 430, 0, 0, 0, 0, 0, 0], 
         [0, 430, 0, 340, 0, 0, 0, 0, 0], 
         [0, 0, 340, 0, 280, 0, 0, 0, 0], 
         [0, 0, 0, 280, 0, 390, 0, 0, 0], 
         [0, 0, 0, 0, 390, 0, 190, 0, 0], 
         [0, 0, 0, 0, 0, 190, 0, 580, 0], 
         [0, 0, 0, 0, 0, 0, 580, 0, 520], 
         [0, 0, 0, 0, 0, 0, 0, 520, 0]]

# 定义起点和终点
start = 0
end = 8

# 初始化距离数组
dist = [float('inf')] * len(graph)
dist[start] = 0

# 初始化堆（小根堆）
heap = [(0, start)]

while heap:
    # 取出距离起点最近的城市
    d, u = heapq.heappop(heap)
    # 如果该城市已经被访问过，则跳过
    if d > dist[u]:
        continue
    # 遍历与该城市相邻的城市
    for v in range(len(graph)):
        if graph[u][v] > 0:
            # 计算通过 u 到达 v 的距离
            alt = dist[u] + graph[u][v]
            # 如果通过 u 到达 v 的距离比当前的最短距离小，则更新 v 的最短距离
            if alt < dist[v]:
                dist[v] = alt
                heapq.heappush(heap, (alt, v))

# 输出从起点到终点的最短距离
print(dist[end])

输出结果为：

520

说明通过所有城市到达目的地的最短距离为 520 百公里。