【算法】图论 —— Dijkstra算法 python

引入

求非负权边的单源最短路

时间复杂度 O( $m l o g n$ )

模板

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))