Dijkstra算法——Python

Dijkastra是常见的求单源最短路的算法，这里将介绍两种最短路的写法。

算法流程：

• 每次扩展一个当前已知最短路径节点
• 扩展这个节点的时候重新计算到达其他节点的最短距离

原因（理论证明）：

• 假设我们有1、2、3三个点，我们计算1到2、3点的最短距离。
• 我们首先加入1，因为1到自己的距离为0，这时候扩展1，计算从1可以到达节点的距离。
• 假设1可以到达2，也可以到达3，我们就可以得到从1直接到达2和3的距离。
• 然后回到第一步，我们直接得到2和3中数值较小的那一个，假设为2，那么我们就认为1到2的最短距离就是这个距离。

为什么？我们使用反证法来证明：

• 如果认为1–>2的距离不是最短的，说不定1–>3–>2可以更短呢？
• 这是不可能的，因为1–>2的距离已经比1–>3短了，1–>3 + 3–>2的距离肯定小于1 --> 2的距离。
• 因此我们每次只需扩展当前已知最短路径中最短的那个点即可，从其他比他长的路径绕到这个点肯定不会更短。

Python代码：

n, m = map(int, input().split())

graph = [[999999] * (n+1) for _ in range(n+1)]

for i in range(m):
    a,b,d = map(int, input().split())
    graph[a][b] = min(graph[a][b], d)

# 是否成为了最短路径点
st = [False] * (n+1)
# 当前最短距离
dis = [999999] * (n+1)

dis[1] = 0

for i in range(1, n+1):
    t = -1
    # 寻找未被拓展的最短的点
    for j in range(1, n+1):
        # 首先要没有被拓展，其次最短
        if not st[j] and (t == -1 or dis[j] < dis[t]):
            t = j

    # 找到了当前可以拓展的节点t，加入并拓展节点t
    st[t] = True
    for j in range(1, n+1):
        dis[j] = min(dis[j], dis[t]+graph[t][j])

if dis[n] != 999999:
    print(dis[n])
else:
    print(-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

最简单版本的Dijkstra还存在可以优化的地方，在我们每次寻找更新之后，当前可到达的点集中距离最短的那个点时候，每次都需要遍历一遍所有未得到最短距离的点，这个过程是O(n)的，我们可以使用最小堆，来将时间复杂度简化为O(logn)，每次只需要取出堆顶元素即可。

from collections import defaultdict
import heapq

graph = defaultdict(list)

n, m = map(int, input().split())
st = [False] * (n+1)
dis = [-1] * (n+1)
for i in range(m):
    a,b,d = map(int, input().split())
    # 用二元组存
    graph[a].append((d, b))

# 首先加入节点1，距离为0
q = [(0, 1)]

while q:
    # 弹出堆顶元素，一定是当前非已知最短距离点集中最小的
    t = heapq.heappop(q)
    d = t[0]
    node = t[1]
    # 如果t已经计算过最短路径，跳过
    if st[node]:
        continue
    
    # 没有被计算过，设置为最短并且拓展
    dis[node] = d
    st[node] = True
    for dis_, node_ in graph[node]:
        if not st[node_]:
            heapq.heappush(q, (d+dis_, node_))

print(dis[n])
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