最短路

带负权的最短路

不能直接应用 Dij 。

反例：

1 2 3
1 3 9
3 2 -100

一种容易想到的方法是给所有边的边权同时加上一个正数 x，从而让所有边的边权均非负。如果新图上起点到终点的最短路经过了 k 条边，则将最短路减去 kx 即可得到实际最短路。

但这样的方法是错误的。考虑下图:

1 4 2
4 2 -3
1 5 0
5 3 2
3 2 -4

此时，可以利用 Johnson 算法 进行处理。

我们新建一个虚拟节点（在这里我们就设它的编号为 0）。从这个点向其他所有点连一条边权为 0 的边。

Q：

SPFA 是被更新 n 次算 负权环 还是 入队n 次算负权环？