bellman-ford算法
bellman-ford算法和SPFA算法是用是单源的背景下且存在负权边情况下使用。整体来说，SPFA是优于bellman-ford算法的，但是对于边数有限制的最短路问题，就只能用bellman-ford算法了
例题描述——有边数限制的最短路
传送门
参考代码(C++版本)
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 510 , M = 10010; int n,m,k; int dist[N]; int backup[N]; //存放点和权重的结构体 struct Edge{ int a,b,w; }edges[M]; void bellman_ford() { //初始化环节 memset(dist,0x3f,sizeof dist); dist[1] = 0; //迭代k条边 for(int i = 0 ; i < k ; i++) { //备份 memcpy(backup,dist,sizeof dist); //处理每条边上存在的最短路 for(int j = 0; j < m;j++) { //获取每个点的信息 int a = edges[j].a,b = edges[j].b,w = edges[j].w; //找最短路径 dist[b] = min(dist[b],backup[a]+w); } } } int main() { //输入 scanf("%d%d%d",&n,&m,&k); //建图 for(int i = 0; i < m ;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); edges[i] = {a,b,w}; } //调用函数 bellman_ford(); //输出结果 if(dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else printf("%d\n",dist[n]); return 0; }
算法模板
bellman-ford算法实现的流程图如下：
bellman-ford算法代码描述如下：
int n, m; // n表示点数，m表示边数 int dist[N]; // dist[x]存储1到x的最短路距离 struct Edge // 边，a表示出点，b表示入点，w表示边的权重 { int a, b, w; }edges[M]; void bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i < n; i ++ ) { for (int j = 0; j < m; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] > dist[a] + w) dist[b] = dist[a] + w; } } }
细节落实
一、备份——为了保证边数限制的条件可以不被打破
memcpy(backup,dist,sizeof dist);
为了避免这种，虽然确实是在外层循环运行的边数k下进行的操作，但是内层循环去探索点的时候，发生类似的情况，所以采取了备份了操作，来遏制这种情况
SPFA 算法
spfa在国际上通常是称呼的是"队列优化的Bellman-Ford"算法
例题描述
参考代码(C++版本）
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int n, m; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } void spfa() { //初始化环节 memset(dist, 0x3f, sizeof dist); dist[1] = 0; //创建一个队列，并将已经确认最短路径的一号点入队 queue<int> q; q.push(1); //标记已经入队的点 st[1] = true; //当队列不空的时候执行系列操作 while (q.size()) { //获取队头，将队头出队 int t = q.front(); q.pop(); //标记不在队列中的点 st[t] = false; //用队头去探索它的出边 for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { //符合条件，更新从1号点到j的距离 dist[j] = dist[t] + w[i]; //如果这个点没有在队列中 if (!st[j]) { //入队，标记 q.push(j); st[j] = true; } } } } } int main() { //输入 scanf("%d%d", &n, &m); //初始化邻接表 memset(h, -1, sizeof h); //建图 while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } //调用函数 spfa(); //输出 if (dist[n] == 0x3f3f3f3f) puts("impossible"); else printf("%d\n", dist[n]); return 0; }
算法模板
SPFA算法实现的流程图如下：
SPFA算法的代码描述如下：
int n; // 总点数 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储每个点到1号点的最短距离 bool st[N]; // 存储每个点是否在队列中 void spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入 { q.push(j); st[j] = true; } } } } }
细节落实
一、入队与标记
在用t更新到新的点j以后，记得判断这个点有没有被标记过，假如没有，将它加入队列并放入st数组进行标记
二、联想记忆
SPFA的本质是用队列优化了bellman-ford算法，但是在实现上有长得很像堆优化版本的dijkstra算法，SPFA用的队列，dijkstra用的优先队列
Floyd算法
为了求出图中任意两点之间的最短路径，也就是最短路大纲中的多源汇最短路问题。对于求任意两点之间的最短路问题，图一般都比较稠密，实现也很简单暴力。
Floyd算法的思想：
把多源的最短路拆分成N次的单源最短路。
单源最短路在Dijkstra算法中是用了两个循环，时间复杂度是O(n2),Floyd这里就在最外层套一层循环N，所以时间复杂度也就是O(n3)
例题描述
参考代码(C++版本)
#include <cstring> #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 210,INF = 1e9; int n,m, Q; int d[N][N]; void floyd() { for(int k = 1; k <= n;k++) for(int i = 1; i <= n;i++) for(int j = 1;j <= n;j++) d[i][j] = min(d[i][j],d[i][k]+d[k][j]); } int main() { scanf("%d%d%d",&n,&m,&Q); //初始化邻接矩阵 for(int i = 1;i <= n;i++) for(int j = 1; j <= n;j++) if(i == j) d[i][j] = 0; else d[i][j] = INF; //创建图 while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); d[a][b] = min(d[a][b],c); } //调用函数 floyd(); //处理Q次询问 while(Q--) { int a,b; scanf("%d%d",&a,&b); if(d[a][b] > INF / 2) puts("impossible"); else printf("%d\n",d[a][b]); } return 0; }
算法模板
Floyd算法实现的流程图：
Floyd算法代码描述：
初始化： for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; // 算法结束后，d[a][b]表示a到b的最短距离 void floyd() { for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }
细节落实
一、初始化
if (i == j) d[i][j] = 0; else d[i][j] = INF;
d数组表示的是从i到j的距离，所以初始化的时候，要将i == j的时候，初始化为0，其他位置初始化为一个无穷大的数
二、输出
因为边权可以为负，所以d[a][b]不一定还是INF了，因此判断条件改为d[a][b]仍然是一个比较大的数就行
if(d[a][b] > INF / 2) puts("impossible"); else printf("%d\n",d[a][b]);
