算法基础之Dijkstra、bellman-ford、spfa、Floyd

1、大纲

朴素版dijkstra：和边数没有关系，和点数有关系。 比较适合边数多的时候 边数和n^2一个级别的时候 稠密图。（点是n，边是m）
堆优化版dijkstra：边数和点数是一个级别。假设n是1e5.则朴素o(n^2)超出时间要求。mlogn恰好适合。

2、单源最短路径

2.1、Dijkstra 正权边

2.1.1 朴素Dijkstra做法

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 510;int n, m;
//稠密图，使用邻接矩阵
int g[N][N];
//从1号点走到n号的距离
int dist[N];
//集合s，已经确定最短路的点
bool st[N];int dijkstra()
{
    
//将1好的点的距离初始化成0，其余所有点到1号点的距离是正无穷memset(dist, 0x3f, sizeof dist);dist[1] = 0;
//循环n次for (int i = 0; i < n ; i ++ ){
    int t = -1;//在所有没有找到最小值的点中，找到一个离1号点距离最小的点。for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;st[t] = true;//由这个点更新其它点的距离值 。for (int j = 1; j <= n; j ++ )//只需要更新不在集合s中的点//没有找到距离1号点最短距离的点if(!st[j])dist[j] = min(dist[j], dist[t] + g[t][j]);}//为什么>=,而不是>,因为存在正权自环if (dist[n] >= 0x3f3f3f3f) return -1;return dist[n];
}int main()
{
    scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) g[i][j] = 0;else g[i][j] = 0x3f3f3f3f;//最短路径中，自环问题没有影响//重边只保留最小的while (m -- ){
    int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = min(g[a][b], c);}printf("%d\n", dijkstra());return 0;
}

邻接矩阵：输入是输入最小
邻接表：代码处理

邻接矩阵两种不同的初始化方法

2.1.2、堆优化后的dijkstra算法

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;//pair的第一个int表示距离，第二个int表示点的编号
typedef pair<int, int> PII;const int N = 15e4 + 10;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 ++ ;
}int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);dist[1] = 0;//小根堆priority_queue<PII, vector<PII>, greater<PII>> heap;//将起点 距离是1 编号是0插入队列heap.push({
    0, 1});while (heap.size()){
    //小根堆是确保在堆中距离最短的点输出auto t = heap.top();heap.pop();//ver是点的编号 distance是该点距离起点的距离int ver = t.second, distance = t.first;//4.较小的边已经输出更新过其它的边，较大的重边直接过滤。if (st[ver]) continue;st[ver] = true;//当前这个点更新与它相连的其它点//1.有重边，在一个链表上，同时执行下列循环for (int i = h[ver]; i != -1; i = ne[i]){
    int j = e[i];//如果小的重边在后执行以上思路。//大的重边在后，这一步直接结束。if (dist[j] > dist[ver] + w[i]){
    dist[j] = dist[ver] + w[i];//2.n条重边如果比n-1条小，依然放进堆//3.堆是小根堆，较小的先输出//priorityqueue 实现堆，无法修改，所以只能插入，产生//冗余数据，但是小根堆，较小的数据排在上方。heap.push({
    dist[j],j});}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}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);}cout << dijkstra() << endl;return 0;
}

时间复杂度 o(mlog n)

2.2、bell-man ford 负权边

2.2.1、有边数限制的最短路

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 510, M = 10010;struct Edge
{
    
//a起点 b终点 c权重int a, b, c;
}edges[M];int n, m, k;
int dist[N];
//备份上一次的dist数据
int last[N];void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);dist[1] = 0;//不超过k条边，迭代不超过k次for (int i = 0; i < k; i ++ ){
    //备份上一次的数据memcpy(last, dist, sizeof dist);//更新每条边for (int j = 0; j < m; j ++ ){
    //使用备份数据是为了防止串联//例如：存在边关系1->2->3//假设1->2的边更改了,2->3随着1->2的更改而更改//而此时要求2->3的更改是在原始数据的dist[2] dist[3]//和边的权值之间更改的，不是利用新数据更改。auto e = edges[j];//由于存在重边或者自环问题 只能是dist[e.b] 不能是last[e.b]dist[e.b] = min(dist[e.b], last[e.a] + e.c);}}
}int main()
{
    scanf("%d%d%d", &n, &m, &k);for (int i = 0; i < m; i ++ ){
    int a, b, c;scanf("%d%d%d", &a, &b, &c);edges[i] = {
    a, b, c};}bellman_ford();if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");else printf("%d\n", dist[n]);return 0;
}

为什么备份

2.3、 spfa 负权边

2.3.1、spfa求最短路

大部分用dijkstra堆优化的算法，可以使用spfa过掉。

#include <cstring>
#include <iostream>
#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 ++ ;
}int 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]){
    dist[j] = dist[t] + w[i];if (!st[j]){
    q.push(j);st[j] = true;}}}}return dist[n];
}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);}int t = spfa();if (t == 0x3f3f3f3f) puts("impossible");else printf("%d\n", t);return 0;
}

2.3.2、spfa判断负环

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;const int N = 2010, M = 10010;int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[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 ++ ;
}bool spfa()
{
    queue<int> q;//因为求的是有没有负环，不是距离的绝对值，可以不赋初值。//判断的是是否存在负环，而不是从1开始的负环，需要将所有的点全部加进去。for (int i = 1; i <= n; i ++ ){
    st[i] = true;q.push(i);}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]){
    dist[j] = dist[t] + w[i];cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true;if (!st[j]){
    q.push(j);st[j] = true;}}}}return false;
}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);}if (spfa()) puts("Yes");else puts("No");return 0;
}

3、多源最短路径 floyd

#include <cstring>
#include <iostream>
#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();while (Q -- ){
    int a, b;scanf("%d%d", &a, &b);int t = d[a][b];/*可能存在负权边，所以当 dist[i][j] = INF, dist[i][k] = INF,dist[k][j] = -10时，那么dist[i][j]就会被更新成INF - 10，但此时i和j仍然是不连通的。*/if (t > INF / 2) puts("impossible");else printf("%d\n", t);}return 0;
}