目录
Bellman_ford之判断负权回路
- 题目链接：卡码网：95. 城市间货物运输 II
文章讲解：代码随想录
某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。
网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；
权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。
然而，在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时，存在一种情况：图中可能出现负权回路。
负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。
为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴，算法还需检测这种特殊情况。
请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。
城市 1 到城市 n 之间可能会出现没有路径的情况
【输入描述】
第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。
接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。
【输出描述】
如果没有发现负权回路，则输出一个整数，表示从城市 1 到城市 n 的最低运输成本（包括政府补贴）。
如果该整数是负数，则表示实现了盈利。如果发现了负权回路的存在，则输出 "circle"。如果从城市 1 无法到达城市 n，则输出 "unconnected"。
输入示例
4 4 1 2 -1 2 3 1 3 1 -1 3 4 1输出示例
circle
思路
常规
本题是 kama94.城市间货物运输I 延伸题目。
本题是要我们判断 负权回路，也就是图中出现环且环上的边总权值为负数。
如果在这样的图中求最短路的话， 就会在这个环里无限循环 （也是负数+负数 只会越来越小），无法求出最短路径。
所以对于 在有负权值的图中求最短路，都需要先看看这个图里有没有负权回路。
接下来我们来看 如何使用 bellman_ford 算法来判断 负权回路。
在 kama94.城市间货物运输I 中 我们讲了 bellman_ford 算法的核心就是一句话：对 所有边 进行 n-1 次松弛。 同时文中的 【拓展】部分， 我们也讲了 松弛n次以上 会怎么样？
在没有负权回路的图中，松弛 n 次以上 ，结果不会有变化。
但本题有 负权回路，如果松弛 n 次，结果就会有变化了，因为 有负权回路 就是可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。
那么每松弛一次，都会更新最短路径，所以结果会一直有变化。
（如果对于 bellman_ford 不了解的录友，建议详细看这里：kama94.城市间货物运输I）
以上为理论分析，接下来我们再画图举例。
我们拿题目中示例来画一个图：
图中 节点1 到 节点4 的最短路径是多少（题目中的最低运输成本） （注意边可以为负数的）
节点1 -> 节点2 -> 节点3 -> 节点4，这样的路径总成本为 -1 + 1 + 1 = 1
而图中有负权回路：
那么我们在负权回路中多绕一圈，我们的最短路径 是不是就更小了 （也就是更低的运输成本）
节点1 -> 节点2 -> 节点3 -> 节点1 -> 节点2 -> 节点3 -> 节点4，这样的路径总成本 (-1) + 1 + (-1) + (-1) + 1 + (-1) + 1 = -1
如果在负权回路多绕两圈，三圈，无穷圈，那么我们的总成本就会无限小， 如果要求最小成本的话，你会发现本题就无解了。
在 bellman_ford 算法中，松弛 n-1 次所有的边 就可以求得 起点到任何节点的最短路径，松弛 n 次以上，minDist数组（记录起到到其他节点的最短距离）中的结果也不会有改变 （如果对 bellman_ford 算法 不了解，也不知道 minDist 是什么，建议详看上篇讲解kama94.城市间货物运输I）
而本题有负权回路的情况下，一直都会有更短的最短路，所以 松弛 第n次，minDist数组 也会发生改变。
那么解决本题的 核心思路，就是在 kama94.城市间货物运输I 的基础上，再多松弛一次，看minDist数组 是否发生变化。
拓展
本题可不可 使用 队列优化版的bellman_ford（SPFA）呢？
上面的解法中，我们对所有边松弛了n-1次后，在松弛一次，如果出现minDist出现变化就判断有负权回路。
如果使用 SPFA 那么节点都是进队列的，那么节点进入队列几次后 足够判断该图是否有负权回路呢？
在 0094.城市间货物运输I-SPFA 中，我们讲过 在极端情况下，即：所有节点都与其他节点相连，每个节点的入度为 n-1 （n为节点数量），所以每个节点最多加入 n-1 次队列。
那么如果节点加入队列的次数 超过了 n-1次 ，那么该图就一定有负权回路。
方法一： Bellman_ford-超时
def main():
n,m = map(int,input().split())
grid = []
for i in range(m):
start,end,val = map(int,input().split())
grid.append([start,end,val])
minDist = [float('inf')] * (n+1)
start = 1
end = n
minDist[start] = 0
flag = False
for i in range(1,n+1):
for side in grid:
from_node = side[0]
to = side[1]
price = side[2]
if i < n:
if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:
minDist[to] = minDist[from_node] + price
else: # 多加一次松弛判断负权回路
if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:
flag = True
if flag:
print('circle')
elif minDist[end] == float('inf'):
print('unconnected')
else:
print(minDist[end])
if __name__=="__main__":
main()方法二：Bellman_ford 2
import sys
def main():
input = sys.stdin.read
data = input().split()
index = 0
n = int(data[index])
index += 1
m = int(data[index])
index += 1
grid = []
for i in range(m):
p1 = int(data[index])
index += 1
p2 = int(data[index])
index += 1
val = int(data[index])
index += 1
# p1 指向 p2，权值为 val
grid.append([p1, p2, val])
minDist = [float('inf')] * (n+1)
start = 1
end = n
minDist[start] = 0
flag = False
for i in range(1,n+1):
for side in grid:
if i < n:
if minDist[side[0]] != float('inf') and minDist[side[1]] > minDist[side[0]] + side[2]:
minDist[side[1]] = minDist[side[0]] + side[2]
else:
if minDist[side[0]] != float('inf') and minDist[side[1]] > minDist[side[0]] + side[2]:
flag = True
if flag:
print('circle')
elif minDist[end] == float('inf'):
print('unconnected')
else:
print(minDist[end])
if __name__=="__main__":
main()方法三：Bellman_ford 队列优化
from collections import deque
class Edge:
def __init__(self,to,val) -> None:
self.to = to
self.val = val
def main():
n,m = map(int,input().split())
grid = [[] for _ in range(n+1)]
for i in range(m):
start,end,val = map(int,input().split())
grid[start].append(Edge(end,val))
start = 1
end = n
que = deque()
que.append(1)
minDist = [float('inf')] * (n+1)
minDist[start] = 0
count = [0] * (n+1)
count[start] +=1
flag = False
while que:
cur_node = que.popleft()
for edge in grid[cur_node]:
if minDist[cur_node] + edge.val < minDist[edge.to]:
minDist[edge.to] = minDist[cur_node] + edge.val
que.append(edge.to)
count[edge.to] +=1
if count[edge.to] == n:
flag = True
while que: que.popleft()
break
if flag:
print("circle")
elif minDist[end] != float("inf"):
print(minDist[end])
else:
print("unconnected")
if __name__ == "__main__":
main()