Bellman-Ford 最短路

				
					
					1
					procedure BellmanFord(G, s)
				
			
				
					
					2
					  dist[s] ← 0; 其余顶点 dist[v] ← ∞
				
			
				
					
					3
					  for i = 1 to n-1 do
				
			
				
					
					4
					    for each 边 (u, v, w) do
				
			
				
					
					5
					      if dist[u] + w < dist[v] then dist[v] ← dist[u] + w   // 松弛
				
			
				
					
					6
					    if 本轮无任何更新: break              // 提前收敛
				
			
				
					
					7
					  if 第 n-1 轮仍能更新: 图含负权环