#953. [笔记]图论II_最短路

    ID: 953 Type: Default 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>图结构最短路DijkstraSPFA图论笔记FloyedBellman-Ford

[笔记]图论II_最短路

No testdata at current.

No submission language available for this problem.

数据结构应用——图论 II 最短路

问题特点

求解图论问题中，两点之间权值和最值问题。（多数情况是最小值问题，偶会出现求解最大值问题）

图论中最短路算法是最常见问题模型以及其它算法的基础，如图上动规往往会有最短路的影子，特别是 Floyed 算法是由动规划分阶段而得。

最短路算法：

多源最短路：计算任意两点之间的最短路

  • Floyed-Warshall O(N3)O(N^3)

单源最短路：计算起点到其它点之间的最短路

  • Dijkstra O(N2)O(N^2)
  • Bellman-Ford O(NE)O(NE)
  • SPFA O(kE)O(kE)

设计图1：

image

// + 表示有向边 - 表示无向边
3 3
- 1 2 3
- 1 3 2
+ 2 3 2

设计图2：

image

// + 表示有向边 - 表示无向边
3 3
- 1 2 3
- 1 3 2
+ 2 3 -2

设计图3：

image

// + 表示有向边 - 表示无向边
3 4
- 1 2 3
- 1 3 2
+ 2 3 -2
+ 3 2 -2
// 最后两条边，相当于一条无向边，边权为 -2
// 即 - 2 3 -2

一、Floyed-Warshall

作为最简单的最短路算法，只是写法上相对简单。

核心思想：计算两点间最短路时，发现可以通过第三个点绕路会更优，则更新两点间最短路。另 g[i][j] 表示顶点 ii 到顶点 jj 的最短路径，数学释义为：

g[i][j]=min{g[i][j],g[i][k]+g[k][j]};g[i][j] = min\{g[i][j], g[i][k] + g[k][j]\};

简单证明（动态规划）

确定状态：令 g[i][j][k]g[i][j][k] 表示以前 kk 个顶点集合获得的 i->j 的最短路长度。

阶段划分：讨论第 kk 个顶点，根据核心思想，即将 i->j 以 i->k->j 方式进行讨论。

g[i][j][k−1]g[i][j][k - 1] 表示 i->j 在前 k−1k - 1 个顶点集合时的最短路

g[i][k][k−1]g[i][k][k - 1] 表示 i->k 在前 k−1k - 1 个顶点集合时的最短路

g[k][j][k−1]g[k][j][k - 1] 表示 k->j 在前 k−1k - 1 个顶点集合时的最短路

状态转移：

$$g[i][j][k] = min\{g[i][j][k - 1], g[i][k][k-1] + g[k][j][k-1]\}; $$

初始化：g[i][j][0] 表示在前 0 个顶点集合时的最短路，即原始图的直接顶点边数据。若 i->j 无边则以无穷大表示无边，且 g[i][i][0] = 0;

计算顺序：

用 g[i][j][0] 计算 g[i][j][1]

用 g[i][j][1] 计算 g[i][j][2]

...

用 g[i][j][k-1] 计算 g[i][j][k]

...

用 g[i][j][N-1] 计算 g[i][j][N]

即最终 g[i][j][N] 表示前 N 个顶点集合时候，i->j 的最短路。

// 设计图 1 的样例代码
#include <bits/stdc++.h>
using namespace std;

const int N = 101;
const int INF = 0x3f3f3f3f;
int g[N][N][N];  // g[N][N][0] 相当于邻接矩阵
int n, m; // n 顶点数，m 边数

int main() {	

	memset(g, 0x3f, sizeof g);

	cin >> n >> m;

	// 正常情况下，不考虑重边与自环
	for (int i = 1; i <= m; i ++) {
		char edge_type; // + 有向边，- 无向边
		int u, v, w;
		cin >> edge_type >> u >> v >> w;
		if (edge_type == '+') {
			g[u][v][0] = w;
			// 若有重边则：g[u][v][0] = min{g[u][v][0], w};
		} else if (edge_type == '-') {
			g[u][v][0] = g[v][u][0] = w;
			// 若有重边则：g[u][v][0] = g[v][u][0] = min(g[u][v][0], w);
		}
	}
	for (int i = 1; i <= n; i ++) 
		g[i][i][0] = 0;

	for (int k = 1; k <= n; k ++) {
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				if (g[i][j][k - 1] > g[i][k][k - 1] + g[k][j][k - 1]) {
					g[i][j][k] = g[i][k][k - 1] + g[k][j][k - 1];
				} else {
					g[i][j][k] = g[i][j][k - 1];
				}
			}
		}
	}

	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			printf("(%2d->%-2d)%-4d ", i, j, g[i][j][n]);
		}
		cout << endl;
	}

    return 0;
}

观察发现，无论从计算过程还是代码过程，[k] 状态只会被 [k - 1] 状态所影响，因此可以用滚动数组思想，等价变换转移方程：

g[i][j]=min{g[i][j],g[i][k]+g[k][j]};g[i][j] = min\{g[i][j], g[i][k] + g[k][j]\};

将三维数组降为二维数组

// 设计图1
#include <bits/stdc++.h>
using namespace std;

const int N = 101;
const int INF = 0x3f3f3f3f;
int g[N][N];  // g[N][N][0] 相当于邻接矩阵
int n, m; // n 顶点数，m 边数

int main() {	

	memset(g, 0x3f, sizeof g);

	cin >> n >> m;

	// 正常情况下，不考虑重边与自环
	for (int i = 1; i <= m; i ++) {
		char edge_type; // + 有向边，- 无向边
		int u, v, w;
		cin >> edge_type >> u >> v >> w;
		if (edge_type == '+') {
			g[u][v] = w;
			// 若有重边则：g[u][v] = min{g[u][v], w};
		} else if (edge_type == '-') {
			g[u][v] = g[v][u] = w;
			// 若有重边则：g[u][v] = g[v][u] = min(g[u][v], w);
		}
	}
	for (int i = 1; i <= n; i ++) 
		g[i][i] = 0;

	for (int k = 1; k <= n; k ++) {
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				if (g[i][j] > g[i][k] + g[k][j]) {
					g[i][j] = g[i][k] + g[k][j];
				}
				// if (g[i][j] > g[i][k] + g[k][j]) {
				// 	g[i][j] = g[i][k] + g[k][j];
				// } else {
				// 	g[i][j] = g[i][j];
				// }
			}
		}
	}

	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			printf("(%2d->%-2d)%-4d ", i, j, g[i][j]);
		}
		cout << endl;
	}

    return 0;
}

动规算法属于规划性最优，因此Floyed 可以解决负边权问题。

判负环也比较容易，若出现 g[i][i] < 0 则说明有负环。

二、Dijkstra

单源最短路径中，比较常用的算法，讨论的是从一个起点到其它顶点的最短路问题。

朴素 Dijkstra 可以进一步优化，这里暂不进行讨论优化部分。


核心思想：蓝白点标记+贪心。蓝点表示还未达成最短路的顶点，白点表示已经达成该算法的最短路顶点。

贪心思想：从蓝点中找到离起点最近的一个顶点作为新起点，从它开始遍历所有的邻接边，松弛它的邻接顶点。（类似每次都找一条最短的路行走更新顶点）


通过以上描述：


  • 邻接表存图比较合适该算法。
  • 需要标记数组做蓝白点标记。
  • 需要距离数组记录距起点的距离，初始除了起点为 0，其它都初始化为无穷远。

松弛：单源点为 s，找到一个顶点 u 作为新起点，一条邻接边为u->v: w，可以考虑 s->u->v 是否更优，数学释义则：

dis[v]=min{dis[v],dis[u]+w};dis[v] = min\{dis[v], dis[u] + w\}; 
// 设计图1
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 101;
const int INF = 0x3f3f3f3f;
struct Edge{ int v, w; };

int n, m; // n 顶点数，m 边数

vector<Edge> g[N]; // 邻接表
int dis[N]; // 距离数组
int vis[N]; // 标记数组 0 表示蓝点，1 表示白点
            //        false:蓝点  true:白点

int main() {	

	cin >> n >> m;

	// 正常情况下，不考虑重边与自环
	for (int i = 1; i <= m; i ++) {
		char edge_type; // + 有向边，- 无向边
		int u, v, w;
		cin >> edge_type >> u >> v >> w;
		if (edge_type == '+') { // 有向边是单向边
			g[u].push_back(Edge{v, w});
		} else if (edge_type == '-') { // 无向边是双向边
			g[u].push_back(Edge{v, w});
			g[v].push_back(Edge{u, w});
		}
	}
	
	memset(dis, 0x3f, sizeof dis);
	int s = 1; // 单源起点
	dis[s] = 0;
	
	for (int i = 1; i <= n; i ++) {
		// 找一个最近的点
		int u = -1, minn = INF;
		for (int j = 1; j <= n; j ++) {
			if (vis[j] == 0) { // 蓝点
				if (minn > dis[j]) {
					u = j;
				}
			}
		}

		// 表示找不到近点了，比如单源起点是孤岛，直接退
		if (u == -1) { break; }

		vis[u] = 1; // 将起点标记为白点

		// 遍历邻接边
		for (int j = 0; j < (int)g[u].size(); j ++) {
			int v = g[u][j].v, w = g[u][j].w;
			// 松弛
			if (vis[v] == 1) continue; // 事实上可以删去，但逻辑上就破坏了 Dijkstra 的蓝白标记法
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				// 实际上还可以做前源点记录，如 pre[v] = u;
			}
		}
	}

	for (int i = 1; i <= n; i ++) { printf("%4d ", i); }
	cout << endl;
	for (int i = 1; i <= n; i ++) {
		if (dis[i] == INF) printf("  inf");
		else printf("%4d ", dis[i]);
	}
	cout << endl;
	

    return 0;
}

贪心算法的最优解需要在某条件下的严格证明，对于 Dijkstra 的贪心思路，无法解决负边权问题（设计图2）进而无法判断负环。

三、Bellman-Ford

单源最短路中，考虑到负边与负环问题，Dijkstra 无法解决。于是提出新的单源最短路径算法：Bellman-Ford。


在算法逻辑上，可以认为是对 Dijkstra 的内容递进，底层原理也是蓝白点标记。


核心思路：直接进行图上全边松弛。借由 Dijkstra 原理，一个白点标记松弛后，必然出现下一个白点。而其松弛的方式为松弛该白点所有邻接边。显然某个顶点的邻接边为图上全边的子集，则若进行一次图上全边松弛，至少在图上会出现一个白点。由于起点一开始便是白点，因此只要进行 n - 1 次图上全边松弛即可。


显然在这种解法下，只要出现图上全边松弛中的松弛操作一次都不成功，说明图上最短路已经完成。Bellman 可以解决合理负边权问题，且事实上经常不需要进行 n - 1 次的全边松弛操作，图上最短路就已经完成。（可以使用标记提前退出最短路算法）

但若负边权值过大，或负环，如无向负权边 (设计图3)，由于绕一圈便会令最短路更短，因此松弛操作将在第 n 次全边操作时候还会发生，可由此判是否出现图上负环。

// 所有设计图
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 101;
const int INF = 0x3f3f3f3f;
// 边
struct Edge{ int u, v, w; };

Edge eg[N]; // 边集数组
int ei;     // 边集数量
int dis[N]; // 距离数组
int n, m; // n 顶点数，m 边数

int main() {	

	cin >> n >> m;

	// 正常情况下，不考虑重边与自环
	for (int i = 1; i <= m; i ++) {
		char edge_type; // + 有向边，- 无向边
		int u, v, w;
		cin >> edge_type >> u >> v >> w;
		if (edge_type == '+') { // 有向边是单向边
			eg[++ ei] = Edge{u, v, w};
		} else if (edge_type == '-') { // 无向边是双向边
			eg[++ ei] = Edge{u, v, w};
			eg[++ ei] = Edge{v, u, w};
		}
	}
	
	memset(dis, 0x3f, sizeof dis);
	int s = 1; // 单源起点
	dis[s] = 0;
	
	bool ok;
	// n - 1 次
	for (int i = 1; i <= n - 1; i ++) {
		ok = true; // 松弛标记
		// 全边松弛
		for (int j = 1; j <= ei; j ++) {
			int u = eg[j].u, v = eg[j].v, w = eg[j].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				ok = false; // 有松弛成功
			}
		}
		if (ok) break; // 全边无松弛则直接退
	}

	ok = true;
	for (int j = 1; j <= ei; j ++) {
		int u = eg[j].u, v = eg[j].v, w = eg[j].w;
		if (dis[v] > dis[u] + w) {
			dis[v] = dis[u] + w;
			ok = false; // 有松弛成功
		}
	}

	if (!ok) {
		cout << "有负环" << endl;
	} else {

		for (int i = 1; i <= n; i ++) { printf("%4d ", i); }
		cout << endl;
		for (int i = 1; i <= n; i ++) {
			if (dis[i] == INF) printf("  inf");
			else printf("%4d ", dis[i]);
		}
		cout << endl;

	}


    return 0;
}

四、SPFA

该算法实际上是 Bellman-Ford 的队列优化。Bellman 是进行全边松弛，中间会有很多的 "废操"，即冗余判断。那么既然可知全边松弛可以增加至少一个白点，为了减少冗余，可以直接从单源点 (第一个白点) 出发，做一个可撤销操作的蓝白点标记法，且关注所有相关的邻接边松弛即可。（有点像 Dijkstra + Bellman-Ford）


核心思想：只关心被松弛的顶点，减少无效冗余。


若有比较熟练的 Dijkstra 和 Bellman 的代码构建能力，根据上面的描述，基本可以构建 SPFA 的代码。


构建核心：广搜思想，用队列维护被松弛的顶点（白点），每次取出一个白点标为蓝点进行邻接边松弛操作。


由于 SPFA 是 Bellman 的优化，因此同样可以解决负边权和判负环问题。但对负环的判定方式有所不同，可以对顶点入队列次数进行计数：若某一顶点入队列的次数超过 n 次，则表示有负环。（另一种办法暂不在此处表述）


#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int N = 101;
const int INF = 0x3f3f3f3f;

struct Edge{ int v, w; };

vector<Edge> g[N]; 
int dis[N]; // 距离数组
int vis[N]; // 标记 1 白点 0 蓝点
int cnt[N]; // 顶点进入队列的计数
int n, m; // n 顶点数，m 边数
queue<int> qe;

int main() {

	cin >> n >> m;

	// 正常情况下，不考虑重边与自环
	for (int i = 1; i <= m; i ++) {
		char edge_type; // + 有向边，- 无向边
		int u, v, w;
		cin >> edge_type >> u >> v >> w;
		if (edge_type == '+') { // 有向边是单向边
			g[u].push_back(Edge{v, w});
		} else if (edge_type == '-') { // 无向边是双向边
			g[u].push_back(Edge{v, w});
			g[v].push_back(Edge{u, w});
		}
	}
	
	memset(dis, 0x3f, sizeof dis);
	int s = 1; // 单源起点
	dis[s] = 0;

	// 判负环，也许负环不包含源点
	for (int i = 1; i <= n; i ++) {
		vis[i] = 1;
		cnt[i]++;
		qe.push(i);
	}


	bool ok = true;
	while (!qe.empty() && ok) {
		int u = qe.front();  // 取出一个白点作为起点
		vis[u] = 0;          // 撤销白点作为蓝点，一边下次松弛
		qe.pop();            // 从队列中删去 u 顶点

		for (int j = 0; j < (int)g[u].size(); j ++) {
			int v = g[u][j].v, w = g[u][j].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w; // 松弛成功
				if (vis[v] == 0) {   // 若此刻它是蓝点，标记为白点入队列
					vis[v] = 1;
					qe.push(v);
					cnt[v] ++;
					if (cnt[v] >= n) { // 出现负环
						ok = false;
						break;
					}
				}
			}
		}
	}
	

	if (!ok) {
		cout << "有负环" << endl;
	} else {

		for (int i = 1; i <= n; i ++) { printf("%4d ", i); }
		cout << endl;
		for (int i = 1; i <= n; i ++) {
			if (dis[i] == INF) printf("  inf");
			else printf("%4d ", dis[i]);
		}
		cout << endl;

	}


    return 0;
}

Related

In following homework:

图应用-最短路练习

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  3. Worker 0, 35ms
  4. Powered by Hydro v4.19.1 Community