【笔记】基于链式前向星的图论算法（二） 最短路

Part 1 单源最短路（SSSP）

Dijkstra

Dijkstra只能用于无负权边的图。

设图$G=(V,E)$所有顶点的集合为$V$，起点为$s$,最短路径树中包含的顶点集合为$S$。

在各计算步骤中，我们将选岀最短路径树的边和顶点并将其添加至$S$。

对于各顶点$i$，设仅经由$S$内顶点的$s$到$i$的最短路径成本为$d[i]$，$i$在最短路径树中的父结点为$p[i]$。

• 初始状态下将$S$置空。

  初始化$S$的$d[s] = 0$；除s以外，所有属于V的顶点i的$d[i]=\infty$

• 循环进行下述处理，直至$S=F$为止。

  • 从$V-S$中选岀$d[u]$最小的顶点$u$

  • 将$u$添加$S$至，同时将与$u$相邻且属于$V-S$的所有顶点$v$的值按下述方式更新：

if d[u] + w(u, v) < d[v]
    d[v] = d[u] + w(u, v)
    p[v] = u

伪代码：

dijkstra(s)
    将所有顶点u的color[u]设为WHITE，d[u]初始化为INFTY
    d[s] = 0
    p[s] = -1

    while true
        mincost = INFTY
        for i从0至n-1
            if color[i] != BLACK && d[i] < mincost
                mincost = d[i]
                u = i

        if mincost == INFTY
            break

        color[u] = BLACK

        for v从0至n-1
            if color[v] != BLACK且u和v之间存在边
                if d[u] + M[u][v] < d[v]
                    d[v] = d[u] + M[u][v]
                    p[v] = u
                    color[v] = GRAY

邻接矩阵实现的Dijkstra算法复杂度为$O(|V|^2)$。使用邻接表时，更新最短距离只需访问每条边一次，因此更新最短距离复杂度为$O(|E|)$。
但是要枚举所有顶点来查找下一个使用的顶点，因此最终复杂度还是$O(|V|^2)$。

Dijkstra堆优化

把每个顶点当前的最短距离用堆维护，可以省去松弛和查找操作，直接把节点和数据丢进优先队列。

更新最短距离时，每次从堆中取出的最小值就是下一次要使用的顶点。

在使用堆优化时，加入堆的应为当前将要被更新的点的编号和当前距离；而当距离被更新时，应新加入一个包含当前点的编号和当前距离的节点。

• 在单源最短路的题目中，Dijkstra是最好用的算法。

/*
 * @Author: thyzzs
 * @Date: 2019-11-06 19:00:52
 * @LastEditTime: 2024-03-11 20:38:18
 * @Description: Dijkstra
 */
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <climits>
#define MAX_V 100005

using namespace std;
// typedef pair<int,int> P;
struct edge {
	int to, cost;
};

int V, E, S;
int u, v, w;
edge e;
vector<edge> G[MAX_V];
int d[MAX_V], vis[MAX_V];

void dijkstra(int s) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
	fill(d, d + V, INT_MAX);
	d[s] = 0;
	que.push(make_pair(0, s));
	
	while (!que.empty()) {
		pair<int, int> p = que.top();
		que.pop();
		int t = p.second;
		if (vis[t])
			continue;
		vis[t] = 1;
		for (int i = 0; i < G[t].size(); i++) {
			e = G[t][i];
			if (d[e.to] > d[t] + e.cost) {
				d[e.to] = d[t] + e.cost;
				if (!vis[e.to])
					que.push(make_pair(d[e.to], e.to));
			}
		}
	}
	return;
}

int main() {
	scanf("%d%d%d", &V, &E, &S);
	S--;
	for (int i = 1; i <= E; i++) {
		scanf("%d%d%d", &u, &v, &w);
		u--;
		v--;
		e.to = v;
		e.cost = w;
		G[u].push_back(e);
		//e.to = u;
		//G[v].push_back(e);
	}
	dijkstra(S);
	for (int i = 0; i < V; i++) {
		printf("%d ", d[i]);
	}
	puts("");
	return 0;
}

Bellman-Ford

Bellman-Ford算法基于动态规划的思想，即反复用已有的边来更新最短距离。即如果$d[u] + cost(u, v) < d[v]$则更新d[v]。

因为最短路经过的边数量不超过n − 1，所以至多n − 1次更新后d[x]即为源点S到地图上其余每个点的最短距离。

• d[S] = 0，其余d[x] = INF

• 对于每条边$(u, v)$，如果$d[u] < INF$且$d[u] + cost(u, v) < d[v]$，则$d[v] = d[u] + cost(u, v) < d[v]$

• 循环上一步至多n − 1次

• 对于每条边$(u, v)$，如果$d[u] < INF$且$d[u] + cost(u, v) < d[v]$，则图中存在负权回路

总时间复杂度$O(nm)$

/*
 * @Author: thyzzs
 * @Date: 2019-11-06 19:00:52
 * @LastEditTime: 2024-03-11 20:38:18
 * @Description: Bellman-Ford
 */
#include <cstdio>
#include <iostream>
#include <climits>

#define MAX_E 500005
#define MAX_V 10005

using namespace std;

struct edge {
	int from, to, cost;
};

edge es[MAX_E];

int d[MAX_V];
int V, E, S;

void Bellman_Ford(int s) {
	for (int i = 1; i <= V; i++)
		d[i] = INT_MAX;
	d[s] = 0;
	while (true) {
		bool update = false;
		for (int i = 1; i <= E; i++) {
			edge e = es[i];
			if (d[e.from] != INT_MAX && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				update = true;
			}
		}
		if (!update)
			break;
	}
}

int main() {
	scanf("%d%d%d", &V, &E, &S);
	for (int i = 1; i <= E; i++) {
		scanf("%d%d%d", &es[i].from, &es[i].to, &es[i].cost);
	}
	Bellman_Ford(S);
	for (int i = 1; i <= V; i++) {
		printf("%d ", d[i]);
	}
	puts("");
	return 0;
}

Bellman-Ford队列优化（SPFA）

SPFA队列优化在随机数据下复杂度较优，但在构造数据下容易被卡。

通常来讲，就是有网格套链式菊花图外挂诱导次短路节点就可以用一个数据卡掉所有的SPFA。

Part 2 所有点对间最短路径（APSP）

所有点对间最短路径问题（All Pairs Shortest Path, APSP) 是以图$G = (V, E)$为对象，求$G$中每两点之间的最短路径（距离）的问题。

Dijkstra

如果$G$中不存在权值为负的边，我们可以将各个顶点作为起点执行$|K|$次Dijkstra算法来求解这类问题。

这样做的算法复杂度为$O(|V|^3)$

用优先级队列实现的话可以简化至$O(|V|(|E|+|V|) \log |V|)$

Floyd

使用邻接矩阵存图

先初始化f[i][i] = 0；若i不能到j，f[i][j] = INF

若从i到j有一条边权为a[i][j]的边，则f[i][j] = a[i][j]

Floyd的本质是一个三维的DP，f[k][i][j]表示可以用1到k的点作为中间点从i到j的最短距离。

f[k][i][j] = min(f[k − 1][i][j], f[k − 1][i][k] + f[k − 1][k][j])

而实际我们可以去掉k这一维

f[i][j] = min(f[i][j], f[i][k] + f[k][j])

• 值f[i][j]不变就对应f[k][i][j] = f[k − 1][i][j]

• 值改变就对应f[k][i][j] = f[k − 1][i][k] + f[k − 1][k][j]