最短路

算法 图论/搜索
算法入门
发布日期:   2022-02-11
更新日期:   2022-03-04
文章字数:   2.7k
阅读时长:   12 分
阅读次数:  

图论最短路

最短路总结（截自y总直播）

Dijkstra算法

朴素Dijkstra算法 O(n^2)

Dijkstra算法用于求节1到点n的最短路，适用于稠密图（其时间复杂度与边数m无关）。

对每个点设定一个dist，代表其距离点1的距离，初始化为无穷大，后续再进行更新。令dist[1] = 0，也就是说，此时除dist1以外，其他点的距离是不确定的。

设定一个集合s，表示已经确定最短路的点。首先对n个点，需要进行n次迭代。**1.找到一个t，t为非s集合中距离最小的点（即不确定距离的dist值最小的点）。2.将t点加入到s集合中（表示该点已经确定距离）。3.**用t更新其他点的距离。（有两种情况，1.假设t点后有一点j，j点的最短路是由t走过来的，即dist[t] +g[t] [j]是最短路径。2.j点的最短路不由t走过来，即此时的dist[j]是最短路)。

#include <bits/stdc++.h>
using namespace std;

const int N = 510;

int n, m;
int g[N][N]; // 邻接矩阵存稠密图
int dist[N]; // 每个点距离点1的距离
bool st[N]; // 判断该点是否确定

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;

    for (int i = 0; i < n; i ++ ){ // n个点循环n次

        int t = -1;

        for (int j = 1; j <= n; j ++ ){ // 找未确定的点中dist最小的点
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
            t = j;
        }

        if (t == n && dist[t] != 0x3f3f3f3f) return dist[t];
        else if (t == n && dist[t] == 0x3f3f3f3f) return -1; // 提前结束循环的优化，不加也可
        st[t] = true;

        for (int j = 1; j <= n; j ++ )// 用t更新其他未确定点的距离
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);

    while (m -- ){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

堆优化Dijkstra算法 O(mlogn)

适用于稀疏图，当边数m和点数n相差不多时，其时间复杂度要比O(n^2)小。而因为是稀疏图，我们的储存方式要用邻接表来存

在上面的朴素算法我们可以得到，三步中第一步找不确定距离中最小dist的复杂度为n^2， 而求最小值我们也可以用先前学过的小根堆来维护，每次取出根节点即可。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

int 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;
    heap.push({0, 1});

    while (heap.size()){
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;
        
        if (st[ver]) continue; // 防止产生冗余
        st[ver] = true;

        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];
                heap.push({dist[j], j});
            }
        }

    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- ){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

Dijkstra算法的弊端

Dijkstra算法是基于贪心的思想，前提是每次走的一步都一定是最优的情况，因此并不能处理含有负权边的情况。因为当出现负权边，并不是局部最优解就是全局最优解。

Dijkstra算法的弊端

Bellman_ford算法

bellman_ford算法适用于含负权边的情况中，但是由于它的方法十分简单暴力，在多数情况下不如SPFA算法，但唯一的一点优势是可以利用它处理有限制边数的最短路问题。

松弛操作

对于bellman_ford算法，我们默认只用它处理有显示边数k的情况。首先进行k次循环，表示走k次边，每走一次边，我们都重新更新一次能走到的dist[j]，这一点和dijkstra算法相似，称为松弛操作。bellman_ford算法的本质就是通过不断地遍历进行松弛操作来找到最小边。

dist[b] = min(dist[b], dist[a] + w); // 松弛操作

串联情况

但和dijkstra算法不同的是，针对于有限制边数的最短路情况下，我们每次更新只能更新出离已经确定的点的旁边的一个点，以此来表示一次更新，否则我们更新到第三个点时会使用第二次本次更新过的点进行更新，相当于在一次迭代中进行了两次更新（可以理解为一次走两条边），当最多边数k有限时就不一定符合情况了，这种情况称为串联情况。

负环情况

当存在负权边时，负环情况也有可能出现。负环情况指的是一条含有负权边的环，走完这一个环所需的总边权为负，当出现这种情况，我们就可以通过无限次的走负环来让最小长度为负无穷。因此当出现负环时多数情况是无解的，即不能走到n点处。但当存在负环，但走向n点的必经之路上不存在负环，问题一样有解。

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 10010;

struct Edge
{
    int a, b ,c;
}edges[M]; // 结构体存边

int n, m, k;
int dist[N];
int backup[N]; // 题目有特殊的边数限制，因此在更新时只能更新上次备份，否则会出现串联

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for (int i = 0; i < k; i ++ ){
        memcpy(backup, dist, sizeof dist); // 每次都将上次的dist存到备份里
        for (int j = 0; j < m; j ++ ){
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], backup[e.a] + e.c);
        }
    }
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < m ; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) printf("impossible\n");
    else printf("%d\n", dist[n]);

    return 0;
}

最后的判断条件是0x3f3f3f3f，目的是为了防止出现一个点还未确定最小距离(0x3f3f3f3f)，而与n点之间存在负权边，会将dist[n]更新成小于0x3f3f3f3f的值，所以不能用dist[n] == 0x3f3f3f3f判断。

SPFA算法 O(nm)

Bellman_ford算法过于简单粗暴，在每次走一条边时要遍历所有的边进行更新，而多数的边都是无效更新（都是在0x3f3f3f3f左右变换，不是真正的确定长度)，也就是说，只有一个点的前驱节点变小了，该节点才会变小。

SPFA就是基于BFS的思想，对Bellman_ford算法的更新进行优化。

最短路

#include <bits/stdc++.h>
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;
                }
            }
        }
    }
    printf("%d\n", dist[n]);
    return dist[n];
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    while (m -- ){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if (spfa() == 0x3f3f3f3f) printf("impossible");
    else printf("%d\n", spfa());

    return 0;
}

判断负权环

SPFA算法同样也可以用于判断负权环的存在，这需要我们定义一个cnt数组用来存储对于走到这个点走过的边数。根据抽屉原理，当cnt[j] >= n时，代表我们走到这个点共走过n条边，而n条边必定存在n+1个点，但点数只有n个，因此一定走过了相同编号的点，也必定存在负环。

#include <bits/stdc++.h>
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;

    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()
{
    cin >> n >> m;
    memset (h, -1, sizeof h);

    while (m -- ){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Floyd算法 O(n^3)

用于判断多源最短路，基于动态规划的思想。

#include <bits/stdc++.h>
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 j = 1; j <= n; j ++ ){
            for (int i = 1; i <= n; i ++ ){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main()
{
    cin >> 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;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (Q -- ){
        int a, b;
        cin >> a >> b;
        int t =d[a][b];
        if (t > INF / 2) printf("impossible");
        else printf("%d\n", t);
    } 

    return 0;
}

路径还原

记录一个path数组，当dist数组被更新时，就同步跟新path数组，此处以朴素dijkstra算法为例：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 510;
const int inf = 0x3f3f3f3f;
int g[maxn][maxn];
int st[maxn];
int dist[500010];
int path[500010];
int n, m;

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    memset(path, -1 ,sizeof path);
    
    dist[1] = 0;
    
    for (int i = 1; i <= n; i ++ ){
        int t = -1;
        for (int j = 1; j <= n; j ++ ){
            if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }
        
        st[t] = 1;
        
        for (int j = 1; j <= n; j ++ ){
            if (dist[j] > dist[t] + g[t][j]){
                dist[j] = dist[t] + g[t][j];
                path[j] = t; // 记录
            }
        }
    }
    return dist[n];
}

vector<int> get_path(int x){
    vector<int> p;
    for (; x != -1; x = path[x]) p.push_back(x);
    reverse(p.begin(), p.end()); //p中存下的是n到1的顺序，我们逆反一下顺序。
    return p;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            g[i][j] = (i == j) ? 0 : inf;
        }
    }
    
    for (int i = 1; i <= m; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    
    printf("%d\n", dijkstra());
    vector<int> p = get_path(n);
    for (auto it : p){
        printf("%d ", it);
    }
    return 0;
}
文章作者: Cedeat
文章链接: http://2715992064.github.io/2022/02/11/zui-duan-lu/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Cedeat !
算法 图论/搜索
赏
  目录