【算法】图论 —— Dijkstra算法 python_dijkstra python生成模拟数据

引入

求非负权边的单源最短路

时间复杂度 O($mlogn$)

模板

https://www.luogu.com.cn/problem/P4779

import heapq as hq def dijkstra(s): # dis表示从s到i的最短路  dis = [float(\'inf\')] * (n + 1) # vis表示i是否出队列  vis = [0] * (n + 1) q = [] dis[s] = 0 hq.heappush(q, (0, s)) while q: d, u = hq.heappop(q) if vis[u]:  continue vis[u] = 1 for v, w in g[u]:  dis[v] = min(dis[v], dis[u] + w)  hq.heappush(q, (dis[v], v)) for i in range(1, n + 1): if dis[i] == float(\'inf\'):  dis[i] = -1 return dis[1:] n, m, s= map(int, input().split()) g = [[] for _ in range(n + 1)] for _ in range(m): u, v, w = map(int, input().split()) g[u].append((v, w)) print(*dijkstra(s))

实战演练

L2 001 紧急救援

维护多个数组并得到具体路径

import heapq as hq import sys input = sys.stdin.readline inf = float(\'inf\') def dijkstra(s, ed): q = [] vis = [0] * n dis = [inf] * n pre = [-1] * n cnt = [0] * n # 最短路径数量  res = [0] * n # 能召集的最大救援队数量  dis[s] = 0 cnt[s] = 1 res[s] = a[s] hq.heappush(q, (0, s)) while q: d, u = hq.heappop(q) if u == ed:  return dis[ed], cnt[ed], res[ed], pre if vis[u]:  continue vis[u] = 1 for (v, w) in g[u]:  if dis[v] > dis[u] + w:  dis[v] = dis[u] + w  cnt[v] = cnt[u]  res[v] = res[u] + a[v]  pre[v] = u  hq.heappush(q, (dis[v], v))  elif dis[v] == dis[u] + w:  cnt[v] += cnt[u] # 更新最短路径数量  if res[v] < res[u] + a[v]:res[v] = res[u] + a[v]pre[v] = u return -1, -1, -1, pre n, m, s, ed = map(int, input().split()) a = list(map(int, input().split())) g = [[] for _ in range(n)] for _ in range(m): u, v, w = map(int, input().split()) g[u].append((v, w)) g[v].append((u, w)) # 无向图  dist, cnt, res, pre = dijkstra(s, ed) if dist != -1: print(cnt, res) path = [] while ed != -1: # 从终点回溯路径  path.append(ed) ed = pre[ed] path.reverse() # 反转路径  print(\' \'.join(map(str, path)))

https://www.lanqiao.cn/problems/3818/learning/

import sys import heapq as hq input = sys.stdin.readline def get(c): if c == \'.\': return 0 else: return ord(c) - ord(\'A\') + 1 def dijkstra(): q = [] dis = [[float(\'inf\')] * m for _ in range(n)] vis = [[0] * m for _ in range(n)] dis[x1][y1] = 0 hq.heappush(q, (0, x1, y1)) while q: d, x, y = hq.heappop(q) if x == x2 and y == y2:  return d if vis[x][y]:  continue vis[x][y] = 1 for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:  nx, ny = x + dx, y + dy  if 0 <= nx < n and 0 <= ny < m and a[nx][ny] != \'#\' and not vis[nx][ny]:  dis[nx][ny] = min(dis[nx][ny], dis[x][y] + get(a[nx][ny]))  hq.heappush(q, (dis[nx][ny], nx, ny)) return float(\'inf\') n, m = map(int, input().split()) x1, y1, x2, y2 = map(int, input().split()) x1 -= 1 x2 -= 1 y1 -= 1 y2 -= 1 a = [input() for _ in range(n)] e = int(input()) if e >= dijkstra(): print(\'Yes\') else: print(\'No\')

https://ac.nowcoder.com/acm/contest/99909/E

对于每条边 $(u,v)$，如果这条边在某条最短路上的话，则一定满足:
dis[u] + w + dis[v] == dis[n] ,即$最短路从1到u，再从u到v，再从v到n$。(或者是$u,v$反过来)

import sys input = sys.stdin.readline inf = float(\'inf\') import heapq as hp def dijkstra(s): dis = [inf] * (n + 1) vis = [0] * (n + 1) q = [(0, s)] dis[s] = 0 while q: d, u = hp.heappop(q) if vis[u]:  continue vis[u] = 1 for v, w in g[u]:  if dis[v] > dis[u] + w:  dis[v] = dis[u] + w  hp.heappush(q, (dis[v], v)) return dis t = int(input()) for _ in range(t): n, m = map(int, input().split()) g = [[] for _ in range(n + 1)] edge = [] for i in range(m): u, v, w = map(int, input().split()) g[u].append((v, w)) g[v].append((u, w)) edge.append((u, v, w)) dis1 = dijkstra(1) disn = dijkstra(n) res = [] for u, v, w in edge: # 检查是否在最短路径中  if dis1[u] != inf and disn[v] != inf and (dis1[u] + w + disn[v] == dis1[n]):  res.append(\'1\') elif dis1[v] != inf and disn[u] != inf and (dis1[v] + w + disn[u] == dis1[n]):  res.append(\'1\') else:  res.append(\'0\') print(\'\'.join(res))

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢