Dijkstra, Bellman-fordSPFA, Floyd比较及其例题

Dijkstra: 适用于求单源点最短路，但不能处理负边权。 例1：模版题，见洛谷P4779 https://www.luogu.org/problem/P4779 代码： #include<cstdio> #include<queue> using namespace std; int n, m, s; priority_queue<pair<int, int> > q;//优先队列，pair函数定义一种数据格式“<int, int>”，用"first","second"调用“<>”里的第一个和第二个元素 bool vis[120000]; int dis[120000]; int from[120000], to[120000], d[120000], next[120000], k = 0; void add(int x, int y, int z) { k++; to[k] = y; //这个节点所指向的节点 d[k] = z; //第k个点的边的权值 next[k] = from[x]; //存储第k个点的子节点的编号 from[x] = k; //储存x节点的编号k } int main() { scanf("%d%d%d", &n, &m, &s); for(int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); //存储数据 } for(int i = 1; i <= n; i++) { dis[i] = 1e9; // 赋很大的初值，为了比较得出最短路径 vis[i] = false; //防止重复走相同的路 } dis[s] = 0; q.push(make_pair(0, s)); //用make_pair定义一个这样的数据类型，即(0, s) while(q.empty() == false) { //Dijkstra核心代码 ↓↓↓ int a = q.top().second; q.pop(); if(vis[a] == true) continue; vis[a] = true; for(int i = from[a]; i; i = next[i]) { //★★★不断将i调整为它所连的点 int y = to[i], l = d[i]; if(dis[y] > dis[a] + l){ dis[y] = dis[a] + l; q.push(make_pair(-dis[y], y));//负号不能写漏了！ } } } for(int i = 1; i <= n; i++) { printf("%d ", dis[i]); } return 0; }

2.Bellman-ford / SPFA 它们只是初阶版和进阶版的区别。SPFA只是在Bellman-ford的基础上增加了队列以优化复杂度。 Bellman-ford / SPFA的最大的，最著名的缺点就是容易超内存。所以最近频频出现“刁难”SPFA的题（见洛谷P4779）。 Bellman-ford/SPFA可求单源点最短路，能处理负边权，Bellman-ford / SPFA能判断负环。 在NOI 2018的第一天第一题中，出题人卡了SPFA算法，导致100分变成60分，所以在没有负环、单纯求最短路径时，不建议使用SPFA算法，而是用Dijkstra算法。 例1：Bellman-ford模版：

#include<cstdio> #include<cstring> using namespace std; int a[3600], b[3600], w[3600], dis[3600]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { scanf("%d%d%d", &a[i], &b[i], &w[i]); } int goal; scanf("%d", &goal); memset(dis, 0x3f3f3f, sizeof(dis)); dis[1] = 0; //Bellman-ford核心代码 ↓↓↓ for(int i = 1; i <= n-1; i++) { int check = 0;//优化，避免无用的查找。 for(int j = 1; j <= m; j++) { if(dis[b[j]] > dis[a[j]] + w[j]) { dis[b[j]] = dis[a[j]] + w[j]; check = 1;//如果已更新，则记录下来 } } if(check == 0) break; //如果未更新，则已全部找到其最短路，可提前退出循环 } for(int i = 1; i <= m; i++) { //判断是否有负环 if(dis[b[j]] > dis[a[j]] + w[j]) { printf("有负环\n"); } } printf("%d\n", dis[goal]); return 0; }

例2：见RQNOJ 341 星门跳跃 http://www.rqnoj.cn/problem/341 这个题要注意是无向图，存储和循环时注意一下即可

#include<cstdio>//注意是无向图！ #include<cstring> using namespace std; int a[360000], b[360000], w[360000], dis[360000]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= 2*m; i++) { scanf("%d%d%d", &a[i], &b[i], &w[i]); a[i+1] = b[i]; b[i+1] = a[i]; w[i+1] = w[i]; i += 1; } memset(dis, 0x3f3f3f, sizeof(dis)); dis[1] = 0; for(int i = 1; i <= 2*(n-1); i++) { int check = 0; for(int j = 1; j <= 2*m; j++) { if(dis[b[j]] > dis[a[j]] + w[j]) { dis[b[j]] = dis[a[j]] + w[j]; check = 1; } } if(check == 0) break; } printf("%d\n", dis[n]); return 0; }

例3：SPFA模版：

#include<cstdio> #include<queue> using namespace std; int dis[520000]; int from[520000], to[520000], next[520000], w[520000]; bool vis[520000]; int k = 0; void add(int x, int y, int z) { k++; to[k] = y; w[k] = z; next[k] = from[x]; from[x] = k; } queue<int> q; int main() { int n, m, s; scanf("%d%d%d", &n, &m, &s); for(int i = 0; i < m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } for(int i = 0; i <= 520000; i++) { dis[i] = 2147483647; } q.push(s); dis[s] = 0; while(q.empty() == false) { int now = q.front(); q.pop(); vis[now] = false; for(int i = from[now]; i; i = next[i]) { if(dis[to[i]] > dis[now] + w[i]) { dis[to[i]] = dis[now] + w[i]; if(vis[to[i]] == false) { vis[to[i]] = true; q.push(to[i]); } } } } for(int i = 1; i <= n; i++) { printf("%d ", dis[i]); } return 0; }

3.Floyd: Floyd能求任意两点间的最短路，能处理负边权。 使用时一定要注意数据范围，太大的话会爆空间。 原理是，在两点之间不断找中间点构成新的路径与当前最短路径比较，从而找到最短路径。 例1：见RQNOJ 86 智捅马蜂窝 http://www.rqnoj.cn/problem/86 代码：

#include<iostream>//最好不要用memset！！！注意数据类型！！！ #include<cstdio> #include<cstring> #include<cmath> using namespace std; double dis[120][120]; double x[120], y[120]; int main() { int n; double v; scanf("%d%lf", &n, &v); int z; scanf("%lf%lf%lf", &x[1], &y[1], &z); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { dis[i][j] = 10000000; } } for(int i = 2; i <= n; i++) { //数据初始化，准备计算 int f; scanf("%lf%lf%d", &x[i], &y[i], &f); dis[i][f] = dis[f][i] = sqrt((x[i] - x[f]) * (x[i] - x[f]) + (y[i] - y[f]) * (y[i] - y[f])) / v; for(int j = 1; j < i; j++) { if(x[i] == x[j] && y[i] < y[j]) { dis[j][i] = min(dis[j][i], sqrt((y[j] - y[i]) / 5)); } else if(x[i] == x[j] && y[i] > y[j]){ dis[i][j] = min(dis[j][i], sqrt((y[i] - y[j]) / 5)); } } } //Floyd核心代码 ↓↓↓ for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i != j && dis[i][j] > dis[i][k] + dis[k][j])//i,j之间的当前最短路径与i~k和k~j的最短路径之和比较 dis[i][j] = dis[i][k] + dis[k][j]; } } } printf("%.2lf\n", dis[1][n]); return 0; }

Floyd找最小回路： 见RQNOJ 389 心灵的抚慰 http://www.rqnoj.cn/problem/389 代码：

#include<cstdio> using namespace std; int a[300][300]; int dis[300][300]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 0; i < 300; i++) { for(int j = 0; j < 300; j++) { dis[i][j] = a[i][j] = 0x3f3f3f; } } for(int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); a[x][y] = a[y][x] = dis[x][y] = dis[y][x] = z; } int minn = 0x3f3f3f; for(int i = 1; i <= n; i++) { //i代表中间点 for(int j = 1; j <= n; j++) { for(int k = 1; k <= n; k++) { if(minn > dis[j][k] + a[k][i] + a[i][j]) { minn = dis[j][k] + a[k][i] + a[i][j];//因为路不能重复，故找一个中间点i依次循环找最短回路 } if(j != k && dis[j][k] > dis[j][i] + dis[i][k]) { dis[j][k] = dis[j][i] + dis[i][k]; } } } } if(minn < 0x3f3f3f) printf("%d\n", minn); else printf("He will never come back.\n"); return 0; }