图论笔记 24-01-31

---

Bellman-Ford

时间复杂度$O(m\times n)$。
两点之间最短路最多包含所有点。如果一个点出现两次，就走了环，非负环不划算，负环没有最短路。
包含$k$条边的最短路可以由最多包含$k-1$条边的最短路加一条边来获得,这个操作是“松弛”。
如果某一个点的最短路被更新了，这个点就有能力更新它所连接的点。
当所有边不满足$d_u+w<d_v$时，最短路不会再改变了。每条边进行$n-1$遍“松弛”操作。
检查，如果有一条边还能松弛，则有负环。

for (int i=1; i<=n; ++i) d[i]=INF;
d[s]=0;
for (int i=1; i<=n-1; ++i) {
		for (int j=1; j<=m; ++j) {
				u=e[j].u, v=e[j].v, w=e[j].w;
				if (d[i]<INF) d[v]=min(d[v], d[u]+w); //松弛
		}
}
for (int i=1; i<=m; ++i)
		if (d[e[i].u]+w<d[e[i].v]) ; //存在负环

---

SPFA

全称Shortest Path Faster Algorithm，于1994年被西安交通大学段凡丁发明。
$n\le10^5$，可以有负权，可以判断负环。
时间复杂度$O(k\times m)$，$k$一般小于$2$。

如果一个点没有被改变，再判断能否“松弛”，是没有意义的。只有它被更新了才检查，用这个优化。

建立一个队列，初始点s，将它所更新的点压入队列，不更新的不管它。做完了弹出，取出下一个点继续更新。当这个队列空了，就意味着没有可以更新的点了，结束。
一个点可能多次进入队列，只要被更新就进入队列。每个顶点进入队列不会超过$n$次，如果超过$n$次就意味着存在负环。

手写队列长度为$10\times n$，也可以用长度为$n+1$的循环队列，也可以用STL::queue。

int spfa(int s) {
	queue<int> q; //队列
	memset(cnt, 0, sizeof(cnt)); //进入队列次数
	memset(inq, 0, sizeof(inq)); //标记是否在队列里面
	for (int i=1; i<=n; ++i) d[i]=INF; //最短路
	d[s]=0; //起点距离为0
	cnt[s]=1; //进入队列次数
	q.push(s); //进入队列
	inq[s]=1; //打标记
	while (!q.empty()) {
		int u=q.front(); //取出点
		q.pop(); //弹出
		inq[u]=0; //取消标记
		for (int i=g[u]; i>0; i=e[i].next) { //遍历所连接的点
			int v=e[i].v, w=e[i].w; //改名，减少出错
			if (d[u]+w<d[v]) { //可以松弛
				d[v]=d[u]+w; //更新
				if (!inq[v]) { //如果不在队列里面
					q.push(v); //进入队列
					inq[v]=1; //在队列里，打标记
					cnt[v]++; //进入队列次数+1
					if (cnt[v]>n) return 1; //存在负环
				}
			}
		}
	}
	return 0; //没有负环
}

SLF优化：
Small Label Fiest策略
如果一个点被更新地很短，前面的就会被浪费。
如果点$v$被更新，队首为$t$，且$d_v$<$d_t$，就把$v$放在队首。

int spfa(int s) {
	deque<int> q;  //队列
	memset(cnt, 0, sizeof(s)); //进入队列次数
	memset(inq, 0, sizeof(inq)); //标记是否在队列里面
	for (int i=1; i<=n; ++i) d[i]=INF;  //最短路
	d[s]=0;  //起点距离为0
	cnt[s]=1;  //进入队列次数
	q.push_front(s);  //进入队列
	inq[s]=1;  //打标记
	while (!q.empty()) {
		int u=q.front();  //取出点
		q.pop_front();  //弹出
		inq[u]=0;  //取消标记
		for (int i=g[u]; i>0; i=e[i].next) {  //遍历所连接的点
			int v=e[i].v, w=e[i].w;  //改名，减少出错
			if (d[u]+w<d[v]) {  //可以松弛
				d[v]=d[u]+w;  //更新
				if (!inq[v]) {  //如果不在队列里面
					if (!q.empty()&&d[v]<=d[q.front()]) q.push_front(v);  //如果比队首小，放前面
					else q.push_back(v);  //如果挺大，放后面
					inq[v]=1;  //在队列里，打标记
					cnt[v]++;  //进入队列次数+1
					if (cnt[v]>n) return 1;  //存在负环
				}
			}
		}
	}
	return 0;  //没有负环
}