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

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

题目描述

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

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

输入

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

输出

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

样例输入

1
5 11
1 5 12
5 1 8
1 2 16
2 1 29
5 2 32
2 4 13
4 2 27
1 3 15
3 1 21
3 4 7
4 3 19
5 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

样例输出

8 24 23 30 0
1

提示

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

解答：

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

答案不唯一，必定有更加优化的解法欢迎分享