Python（算法综合）问题 A: 一场说走就走的旅行-最短路径（Dijkstra迪杰斯特拉算法）_python

问题 A: 一场说走就走的旅行-最短路径

题目描述

有一天，孩子回来对我说：“妈妈，听说马尔代夫很不错，放假了我想去玩。”
马尔代夫？我也想去！没有人不向往一场说走就走的旅行！
“其实我想去的地方很多，呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”
小孩子还说着他感兴趣的地方。
于是我们拿出地图，标出想去的地点，然后计算最短路线，估算大约所需的时间，有了这张秘制地图，一场说走就走的旅行不是梦！

    “哇，感觉我们像凡尔纳的《环游地球八十天》，好激动！可是老妈你也太 out 了，学计算机的最短路线你用手算？”暴汗……，“小子你别牛，你知道怎么算？”
    “呃，好像是叫什么迪科斯彻的人会算。”
    哈哈，关键时刻还要老妈上场了！
    
根据题目描述可知，这是一个求单源最短路径的问题。
给定有向带权图 G =（V，Ｅ），其中每条边的权是非负实数。
此外，给定 V 中的一个顶点，称为源点。
现在要计算从源到所有其他各顶点的最短路径长度，这里路径长度指路上各边的权之和。

输入

第一行输入T组样例
第二行输入图的点数n和边数m
接下来m行输入u v w（分别为起点和终点以及边权）
接下来输入小明的位置pos

输出

输出小明到每个点的最短距离 中间用空格分隔 末尾没有空格（对于到不了的地方输出impossible）

样例输入

样例输出

8 24 23 30 0

提示

样例解释：
输出 小明所在的位置：1  小明所在的位置:5
小明:5 - 要去的位置:1 最短距离为:8
小明:5 - 要去的位置:2 最短距离为:24
小明:5 - 要去的位置:3 最短距离为:23
小明:5 - 要去的位置:4 最短距离为:30
小明:5 - 要去的位置:5 最短距离为:0
小明：1 - 要去的位置：5 最短距离为：4

解答：

def Dijkstra(network, s, d):  # 迪杰斯特拉算法，算s-d的最短路径，并返回该路径和代价
    # network：网络拓扑,s：起始节点,d：目的节点
    # print("Start Dijstra Path")
    path = []  # s-d的最短路径
    n = len(network)  # 邻接矩阵维度，即节点个数
    # print("节点个数n{}".format(n))
    fmax = 999
    w = [[0 for i in range(n)] for j in range(n)]  # 邻接矩阵转化成维度矩阵，即0→max
    # print("这个是w{}" .format(w))
    book = [0 for i in range(n)]  # 是否已经是最小的标记列表
    # print("这个是book{}" .format(book))
    dis = [fmax for i in range(n)]  # s到其他节点的最小距离
    dis[s - 1] = 0  # 给起始点到自身的距离重新赋值为0
    # print("这个是dis{}" .format(dis))
    book[s - 1] = 1  # 节点编号从1开始，列表序号从0开始
    midpath = [-1 for i in range(n)]  # 上一跳列表
    # print("这个是midpath{}".format(midpath))
    for i in range(n):
        for j in range(n):
            if network[i][j] != 0:
                w[i][j] = network[i][j]  # 0→max
            else:
                w[i][j] = fmax
            if i == s - 1 and network[i][j] != 0:  # 直连的节点最小距离就是network[i][j]
                dis[j] = network[i][j]
    for i in range(n - 1):  # n-1次遍历，除了s节点
        min = fmax
        for j in range(n):
            if book[j] == 0 and dis[j] < min:  # 如果未遍历且距离最小
                min = dis[j]
                u = j
        book[u] = 1
        for v in range(n):  # u直连的节点遍历一遍
            if dis[v] > dis[u] + w[u][v]:
                dis[v] = dis[u] + w[u][v]
                midpath[v] = u + 1  # 上一跳更新
    j = d - 1  # j是序号
    path.append(d)  # 因为存储的是上一跳,所以先加入目的节点d，最后倒置
    while midpath[j] != -1:
        path.append(midpath[j])
        j = midpath[j] - 1
    path.append(s)
    path.reverse()  # 倒置列表
    # print(path)  # path是路径
    # print(dis)  # dis是到每个位置的最短距离
    for i in range(n):
        print(dis[i], end=" ")


t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    network = [[0 for i in range(n)] for j in range(n)]
    for i in range(m):
        a, b, c = map(int, input().split())
        network[a - 1][b - 1] = c
    start = int(input())
    Dijkstra(network, start, 1)