求最短路径最常用的算法有：
Dijkstra算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法。
Dijkstra算法、SPFA算法、Bellman-Ford算法这三个求单源最短路径，最后一个Floyd-Warshall算法可以求全局最短路径也可以求单源路径，效率比较低。
SPFA算法是Bellman算法的队列优化。
Dijkstra算法不能求带负权边的最短路径，而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
Bellman-Ford算法的核心代码只有4行，Floyd-Warshall算法的核心代码只有5行。
1.最基本的求单源最短路径方法是图的深度优先遍历：
用 min = 99999999 记录路径的最小值，book[i]标记结点 i 是否被访问过~
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> using namespace std; int minn = 99999999; int book[101]; int n; int e[101][101]; //cur是当前所在的城市编号，dis是当前已经走过的路程 void dfs(int cur, int dis) { if (dis > minn) return ; if (cur == n) { if (dis < minn) minn = dis; return ; } for (int i = 1; i <= n; i++) {//从cur到所有结点依次尝试 if (e[cur][i] != 99999999 && book[i] == 0) { book[i] = 1; dfs(i, dis + e[cur][i]);//从i结点出发到其他所有结点依次尝试直到遇到要求的n结点为止 book[i] = 0; } } return ; } int main() { int m; cin >> n >> m; int a, b, c; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) e[i][j] = 0; else e[i][j] = 99999999; } } for(int i = 1; i <= m; i++) { cin >> a >> b >> c; e[a][b] = c; } book[1] = 1; dfs(1, 0); cout << minn; return 0; } |
2.单源最短路径：Dijkstra算法
dis[i]是需要不断更新的数组，它表示当前结点1(源点)到其余各结点的最短路径长度~
book[i]标记当前结点最短路径是确定值还是估计值~
算法实现的过程是：每次找到离结点1最近的那个点，然后以该结点为中心扩展，最终得到源点到所有点的最短路径~~每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质~~
找到所有估计值当中最小的值min以及它的结点u，然后把该结点u标记为确定值，通过这个确定值为中转点更新别的所有值的最短路径(松弛别的两个顶点连接的边)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
//邻接矩阵 int n, e[maxv][maxv]; int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点 bool vis[maxv] = {false}; void Dijkstra(int s) { fill(dis, dis + maxv, inf); dis[s] = 0; for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身 for(int i = 0; i < n; i++) { int u = -1, minn = inf; for(int j = 0; j < n; j++) { if(visit[j] == false && dis[j] < minn) { u = j; minn = dis[j]; } } if(u == -1) return; visit[u] = true; for(int v = 0; v < n; v++) { if(visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] < dis[v]) { dis[v] = dis[u] + e[u][v]; pre[v] = u; // pre用来标注当前结点的前一个结点 } } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
//邻接表 struct node { int v, dis; } vector<node> e[maxv]; int n; int dis[maxv], pre[maxv];// pre用来标注当前结点的前一个结点 bool vis[maxv] = {false}; for(int i = 0; i < n; i++) pre[i] = i; //初始状态设每个点的前驱为自身 void Dijkstra(int s) { fill(d, d + maxv, inf); dis[s] = 0; for(int i = 0; i < n; i++) { int u = -1, minn = inf; for(int j = 0; j < n; j++) { if(visit[j] == false && dis[j] < minn) { u = j; minn = dis[j]; } } if(u == -1) return ; visit[u] = true; for(int j = 0; j < e[u].size(); j++) { int v = e[u][j].v; if(visit[v] == false && dis[u] + e[u][j].dis < dis[v]) { dis[v] = dis[u] + e[u][j].dis; pre[v] = u; } } } } |
3.Bellman-Ford算法——解决负权边
算法思想：对所有的边进行n-1次“松弛”操作
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
核心算法四行： for (k = 1; k <= n - 1; k++) for (i = 1; i <= m; i++) if (dis[v[i]] > dis[u[i]] + w[i]) dis[v[i]] = dis[u[i]] + w[i]; 进行n-1轮的原因：在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边。 //检验负权回路 如果在进行最短路径算法后，仍然有可以松弛的边，那么就是存在负权回路 flag = 0; for (i = 1; i <= m; i++) if (dis[v[i]] > dis[u[i]] + w[i]) flag = 1; if (flag == 1) printf("此图含有负权回路"); |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
如果在新一轮的松弛中数组dis没有发生变化，则可以提前跳出循环 #include <iostream> #include <cstdio> //n个结点，m条边 using namespace std; int main() { int dis[10], bak[10], n, m, u[10], v[10], w[10], check, flag; int inf = 99999999; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d %d %d", &u[i], &v[i], &w[i]); for (int i = 1; i <= n; i++) dis[i] = inf; dis[1] = 0; for (int k = 1; k <= n - 1; k++) { for (int i = 1; i <= n; i++) bak[i] = dis[i];//将dis数组备份入bak数组中，为了下面的检查是否更新而进行剪枝 for (int i = 1; i <= m; i++) if (dis[v[i]] > dis[u[i]] + w[i]) dis[v[i]] = dis[u[i]] + w[i]; check = 0; for (int i = 1; i < n; i++) if (bak[i] != dis[i]) { check = 1; break; } // 如果对于所有的结点，dis的值都没有被更新，那就提前跳出循环，说明不需要进行n-1次了 if (check == 0) break; } //检查是否含有负权回路（可省略） flag = 0; for (int i = 1; i <= m; i++) if (dis[v[i]] > dis[u[i]] + w[i]) flag = 1; if (flag == 1) printf("此图含有负权回路"); else { for (int i = 1; i <= n; i++) printf("%d ", dis[i]); } return 0; } |
4.Bellman-Ford的队列优化(SPFA算法)
每次选取首顶点u，对u的所有出边进行松弛操作~如果有一条u->v的边，通过这条边使得源点到顶点v的路程变短，且顶点v不在当前队列中，就把这个顶点v放入队尾。同一个顶点在队列中出现多次是毫无意义的，所以用一个数组来判重复，判断哪些点已经在队列中。对顶点u的所有出边都松弛完毕后，就将顶点v出队~
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <cstdio> using namespace std; int main() { int n, m; int u[8], v[8], w[8]; int first[6], next[8]; int dis[6] = {0}, book[6] = {0}; int que[101] = {0}; int head = 1; int tail = 1; int inf = 99999999; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) dis[i] = inf; dis[1] = 0; for (int i = 1; i <= n; i++) book[i] = 0; for (int i = 1; i <= n; i++) first[i] = -1; for (int i = 1; i <= m; i++) { scanf("%d %d %d", &u[i], &v[i], &w[i]); next[i] = first[u[i]]; first[u[i]] = i; } que[tail] = 1; tail++; book[1] = 1; int k; while (head < tail) { k = first[que[head]]; while (k != -1) { if (dis[v[k]] > dis[u[k]] + w[k]) { dis[v[k]] = dis[u[k]] + w[k]; if (book[v[k]] == 0) { que[tail] = v[k]; tail++; book[v[k]] = 1; } } k = next[k]; } book[que[head]] = 0; head++; } for (int i = 1; i <= n; i++) printf("%d ", dis[i]); return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
