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

SPFA 算法：求有负权的图的最短路

---

模板

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

import sys  
input = sys.stdin.readline  
inf = float('inf')  from collections import deque  
t = int(input())  
for _ in range(t):  n, m = map(int, input().split())  edge = [[] for _ in range(n + 1)]  for _ in range(m):  u, v, w = map(int, input().split())  if w < 0:  edge[u].append((v, w))  else:  edge[u].append((v, w))  edge[v].append((u, w))  dis = [inf] * (n + 1)  vis = [0] * (n + 1)  cnt = [0] * (n + 1)  # 记录每个点的入队次数  dis[1] = 0  vis[1] = 1  q = deque()  q.append(1)  flag = 0  while q:  u = q.popleft()  vis[u] = 0  for (v, w) in edge[u]:  if dis[v] > dis[u] + w:  dis[v] = dis[u] + w  if not vis[v]:  q.append(v)  vis[v] = 1  cnt[v] += 1  if cnt[v] > n:  # 如果入队次数超过 n，说明存在负环  flag = 1  break  if flag:  break  if flag:  print('YES')  else:  print('NO')

---

实战演练

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

import sys  
input = sys.stdin.readline  
inf = float('inf')  from collections import deque  
n, m = map(int, input().split())  
c = list(map(int, input().split()))  
edge = [[] for _ in range(n)]  
for _ in range(m):  u, v, w = map(int, input().split())  u -= 1  v -= 1  edge[u].append((v, w))  edge[v].append((u, w))  dis = [inf] * n  
vis = [0] * n  
dis[0] = 0  q = deque()  
q.append(0)  
vis[0] = 1  while q:  u = q.popleft()  vis[u] = 0  for v, w in edge[u]:  if v == n - 1:  res = 0  else:  res = c[v]  if dis[v] > dis[u] + w + res:  dis[v] = dis[u] + w + res  if not vis[v]:  q.append(v)  vis[v] = 1  print(dis[n - 1])

---

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