单源最短路径（Dijkstra算法）——Python实现_单源最短路径python

1. 问题描述

Dijkstra算法解决的是带权重的有向图上单源最短路径问题。
所有边的权重都为非负值。
设置顶点集合S并不断地作贪心选择来扩充这个集合。使用最小堆数据结构构造优先队列。
1
2
3

2. 输入形式

在屏幕上输入顶点个数和连接顶点间的边的权矩阵。
1

3. 输出形式

从源到各个顶点的最短距离及路径。
1

4. 样例

4.1 样例输入

5
0 10 0 30 100
0 0 50 0 0
0 0 0 0 10
0 0 20 0 60
0 0 0 0 0
1
2
3
4
5
6

4.2 样例输出

10: 1->2
50: 1->4->3
30: 1->4
60: 1->4->3->5
1
2
3
4

4.3 样例说明

 输入：顶点个数为5;
 	  连接顶点间边的权矩阵大小为5行5列;
 	  位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。
 输出：每行表示源1到其余各顶点的最短距离及路径。
1
2
3
4

5. 问题分析

输入包含了一个有权重的有向图G，然后求从顶点1开始到其他顶点的最短距离；
由输入格式，可得该题有向图如下图所示：

6. 算法的基本思想

Dijkstra算法是解决单源最短路径的一个贪心算法。
其基本思想是：

每次新扩展一个距离最短的点，更新与其相邻的点的距离。
当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。
不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

7. 代码

import numpy as np


def Result(prev, t):
    if prev[t] != 0:
        Result(prev, prev[t])
        print('->{}'.format(prev[t] + 1), end="")


def Dijkstra(n, weights):
    # 创建一个flag数组，用于保存遍历情况
    flag = np.zeros(n, bool)
    # 创建一个dist数组，用于保存最短路径
    dist = np.array(weights[0])
    # 创建一个prev数组，用于保存对应的最短节点
    prev = np.zeros(n, int)
    # 将源节点放入集合S中
    flag[0] = True
    # Dijkstra算法中重点：
    # ~~错误思路：迭代(n+1)/2次，因为每次可以确定两个节点
    # 迭代次数为n-1次，因为如果确定某一节点，但其最小值不会影响其他节点，每次迭代只能确定一个节点；
    # 依次将节点放入集合S中（即已访问过的节点）；
    for i in range(n-1):
        # 找到当前dist中还未被遍历的节点中权值最小的节点；
        # 并将其放入集合S中；
        temp = float('inf')
        u = 0
        for j in range(n):
            if not flag[j] and dist[j] != 0 and dist[j] < temp:
                u = j
                temp = dist[j]
        flag[u] = True
        # 确定当前节点最短距离后，其他节点最短距离是否随之改变，若改变，即可确定其最短路径；
        for j in range(n):
            if not flag[j] and weights[u][j] != 0:
                if dist[u] + weights[u][j] < dist[j] or dist[j] == 0:
                    dist[j] = dist[u] + weights[u][j]
                    prev[j] = u
    # 输出结果
    for i in range(1, n):
        print('{}：1'.format(dist[i]), end="")
        # 递归函数，因为prev中是从后往前读取节点
        Result(prev, i)
        print("->{}".format(i + 1))


def main():
    n = int(input())
    weight = []
    for i in range(n):
        weight.append(list(map(int, input().rstrip().split())))
    weights = np.array(weight).reshape(n, n)
    Dijkstra(n, weights)


if __name__ == '__main__':
    main()

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

*注：CG平台只支持ASCII，不支持UTF-８，所以在输入->这玩意，还是直接复制上面输出示例中的->