94.城市间货物运输 I
https://kamacoder.com/problempage.php?pid=1152
Bellman_ford 队列优化算法（又名SPFA）
https://www.programmercarl.com/kamacoder/0094.城市间货物运输I-SPFA.html
95.城市间货物运输 II
https://kamacoder.com/problempage.php?pid=1153
bellman_ford之判断负权回路
https://www.programmercarl.com/kamacoder/0095.城市间货物运输II.html
96.城市间货物运输 III
https://kamacoder.com/problempage.php?pid=1154
bellman_ford之单源有限最短路
https://www.programmercarl.com/kamacoder/0096.城市间货物运输III.html

94. 城市间货物运输 I — SPFA

• 优化方式

  • 采用队列
  • 只按照边和节点进行遍历（不需要n-1遍）
  点击查看代码

  from collections import deque
  class edge:
  	def __init__(self,t,v):
  		self.to = t
  		self.val = v
  
  def spfa(n,m,edges,start,end):
  	isqueue = [False]*(n+1)
  	mindist = [float("inf")]*(n+1)
  	mindist[start] = 0
  	que = deque([start])
  
  	while que:
  		curr = que.popleft()
  		isqueue[curr] = False
  		if len(edges[curr])>0:
  			for ed in edges[curr]:
  				to = ed.to
  				val = ed.val
  				if mindist[to]>mindist[curr]+val:
  					mindist[to] = mindist[curr]+val
  					if not isqueue[to]:
  						que.append(to)
  						isqueue[to] = True
  
  	if mindist[end]==float("inf"):
  		return "unconnected"
  	else:
  		return mindist[end]
  
  
  def main():
  	n,m = map(int,input().split())
  	edges = [[] for _ in range(n+1)]
  	# print(edges)
  	for _ in range(m):
  		s,t,v = map(int,input().split())
  		edges[s].append(edge(t,v))
  	res = spfa(n,m,edges,1,n)
  	print(res)
  
  if __name__ == '__main__':
  	main()
  

95. 城市间货物运输 II - 判断负权回路

• 问题：判断是否存在负权回路

• 在SPFA中

• 松弛n-1次

  • 如果有没有负权回路，n-1次松弛所有的边能得到起点到节点的最短路径；n次以上minDist数组中的结果不会有改变；
  • 但是如果第n次也改变：说明存在负权回路；
  点击查看代码

  def bellman(n,m,edges,start,end):
  	mindist = [float("inf")]*(n+1)
  	mindist[start] = 0
  	count = [0]*(n+1)
  
  	for i in range(n):
  		update = False
  		for s,t,v in edges:
  			if mindist[s]!=float("inf") and mindist[t]>mindist[s]+v:
  				mindist[t] = mindist[s]+v
  				update = True
  		if not update:
  			break
  
  	for s,t,v in edges:
  		if mindist[s]!=float("inf") and mindist[t]>mindist[s]+v:
  			return "circle"
  
  	if mindist[end]==float("inf"):
  		return "unconnected"
  	else:
  		return mindist[end]
  
  def main():
  	n,m = map(int,input().split())
  	grid = [[float("inf")]*(n+1) for _ in range(n+1)]
  	# print(edges)
  	edges = []
  	for _ in range(m):
  		s,t,v = map(int,input().split())
  		edges.append((s,t,v))
  	res = bellman(n,m,edges,1,n)
  	print(res)
  if __name__ == '__main__':
  	main()
  

• 队列优化

  • 如果某个点更新超过n-1次，说明存在负权回路；
  点击查看代码

  from collections import deque
  class edge:
  	def __init__(self,t,v):
  		self.to = t
  		self.val = v
  
  def spfa(n,m,edges,start,end):
  	isqueue = [False]*(n+1)
  	mindist = [float("inf")]*(n+1)
  	mindist[start] = 0
  	que = deque([start])
  	count = [0]*(n+1)
  
  	while que:
  		curr = que.popleft()
  		isqueue[curr] = False
  		if len(edges[curr])>0:
  			for ed in edges[curr]:
  				to = ed.to
  				val = ed.val
  				if mindist[to]>mindist[curr]+val:
  					mindist[to] = mindist[curr]+val
  					count[to]+=1
  					if count[to]==n:
  						return "circle"
  					if not isqueue[to]:
  						que.append(to)
  						isqueue[to] = True
  
  	if mindist[end]==float("inf"):
  		return "unconnected"
  	else:
  		return mindist[end]
  
  def main():
  	n,m = map(int,input().split())
  	edges = [[] for _ in range(n+1)]
  	# print(edges)
  	for _ in range(m):
  		s,t,v = map(int,input().split())
  		edges[s].append(edge(t,v))
  	res = spfa(n,m,edges,1,n)
  	print(res)
  if __name__ == '__main__':
  	main()
  

96. 城市间货物运输 III

• 限制条件：在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本。

• 分析：

  • 等价于：起点最多经过k + 1 条边到达终点的最短距离

• 松弛n-1次

  • 限制循环k-1次
  • 复制mindist保证每次更新一步
  点击查看代码

  from collections import deque
  
  class edge:
  	def __init__(self,t,v):
  		self.to = t
  		self.val = v
  def spfa(n,m,edges,start,end,k):
  	mindist = [float("inf")]*(n+1)
  	mindist[start]=0
  	isqueue = [False]*(n+1)
  	queue = deque([start])
  	k = k+1
  	while k and queue:
  		k -= 1
  		mindist_copy = mindist[:]
  		visited = [False]*(n+1)
  		que_size = len(queue)
  		for _ in range(que_size):
  			curr = queue.popleft()
  			if len(edges[curr])>0:
  				for ed in edges[curr]:
  					from_ = curr
  					to = ed.to
  					val = ed.val
  					if mindist[to]>mindist_copy[curr]+val:
  						mindist[to] = mindist_copy[curr]+val
  						if not visited[to]:
  							queue.append(to)
  							visited[to] = True
  		# print(mindist)
  	if mindist[end]!=float("inf"):
  		return mindist[end]
  	else:
  		return "unconnected"
  def main():
  	n,m = map(int,input().split())
  	edges = [[] for _ in range(n+1)]
  	# print(edges)
  	for _ in range(m):
  		s,t,v = map(int,input().split())
  		edges[s].append(edge(t,v))
  	src,dst,k = map(int,input().split())
  	res = spfa(n,m,edges,src,dst,k)
  	print(res)
  if __name__ == '__main__':
  	main()
  

• 队列优化

  • 使用visited数组记录遍历过的点
  • 限制遍历次数k
  点击查看代码

  def bellman(n, m, edges, start, end, k):
  	mindist = [float("inf")] * (n + 1)
  	mindist[start] = 0
  	for i in range(1, k + 2):
  		mindist_copy = mindist[:]
  		update = False
  		for s, t, v in edges:
  			if mindist_copy[s] != float("inf") and mindist[t] > mindist_copy[s] + v:
  				mindist[t] = mindist_copy[s] + v
  				update = True
  		if not update:
  			break
  	if mindist[end] == float("inf"):
  		return "unreachable"
  	else:
  		return mindist[end]
  def main():
  	n, m = map(int, input().split())
  	edges = []
  	for _ in range(m):
  		s, t, v = map(int, input().split())
  		edges.append((s, t, v))
  	src, dst, k = map(int, input().split())
  	res = bellman(n, m, edges, src, dst, k)
  	print(res)
  if __name__ == '__main__':
  	main()