首页 > 其他分享 >最短路总结

最短路总结

时间：2023-08-18 12:34:05浏览次数：46  
标签：总结 松弛 int 短路 operatorname LL dis

最短路径

目录

\(\operatorname{Floyd}\)（全源最短路）

我们定义一个数组 \(f_{k,x,y}\) 表示只经过节点 \(1\) ~ \(k\) 的情况下，\(x\) 到 \(y\) 的最短路长度，那么显然的，当一个图中节点个数为 \(n\) 时，\(f_{n,x,y}\) 就是我们所要求的答案。实现 \(\operatorname{Floyd}\) 算法需要我们从 \(k=0\) 时的情况逐渐递推到 \(k=n\)。\(k=0\) 时，\(x\) 和 \(y\)​ 不相等的情况下不可能通过任何情况联通，而一个点到自己的距离显然为 \(0\)，所以我们认为：

\[\left\{\begin{matrix} f_{0,x,y}(x \ne y)=\infty \\ f_{0,x,y}(x=y)=0 \end{matrix}\right. \]

于是我们就得到了递推式的第一项，我们考虑动态规划。对于每一个点，我都有两种选择：第一种是经过这个点，即 \(f_{k-1,x,y}\)；而第二种是不经过这个点，即 \(f_{k-1,x,k}+f_{k-1,k,y}\) 。我们寻找最短路时只要判断经过当前的点的代价和不经过当前点的代价哪个更小就可以了，所以 \(k,x,y\) 都从 \(1\) 开始枚举一遍就可以得出答案，下面是具体实现（切勿忘记初始化）：

for (int k = 1; k <= n; ++k) {
	for (int x = 1; x <= n; ++x) {
		for (int y = 1; y <= n; ++y) {
            f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k] +f[k-1][k][y]);
        }
    }
}

因为 \(f_{k-1,x,y}\) 表示的就是当 \(k-1\) 这一维中所有元素的最小值，那么该维其它值对于我们来说没有贡献，我们就可以考虑把这一维去掉，将三维数组压缩成二维数组，像这样：

for (int k = 1; k <= n; ++k) {
	for (int x = 1; x <= n; ++x) {
		for (int y = 1; y <= n; ++y) {
            f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
        }
    }
}

最终我们算法的时间复杂度为 \(O(n^3)\)，空间复杂度为 \(O(n^2)\)，常数很小。但是我们发现，当我们要求单源最短路时，这种方法求出的其它最短路对于我们来说就是一种浪费，但这又是无法避免的，所以我们考虑，对于单源最短路有没有其它的做法。

\(\operatorname{Dijkstra}\)（非负权图单源最短路）

\(\operatorname{Dijkstra}\) 算法将一张图内所有结点分为了两个集合，其中一个集合内放已经确定了起点到其的最短路的点，另一个放还没有确定最短路的点，我们分别记为 \(S\) 和 \(T\) 。为了记录源点到每个点的最短路，我们要用一个数组 \(dis\)。刚开始的时候所有的点都属于集合 \(T\)，接下来，每一次操作都从 \(T\) 中取出最短路长度最小的点放入 \(S\) 集合中，对其进行松弛操作，什么是松弛呢？我们进行如下定义：对于一条边\((u,v)\)，设其边权为 \(w\) ，则 \(dis_v = min(dis(v),dis(u) + w)\)。这个操作就叫做松弛，而它的含义是显而易见的，就是当我们走到一个点的时候考虑要不要去走某一条边。

那么如何维护这两个集合呢？我们考虑用一个 \(used\) 数组来记录当前点以前是否更新过，也就是说记录其是否在集合 \(S\) 中。然后每次遍历找到 \(T\) 中最小的那个点，对它所有出边进行松弛即可，下面是代码实现：

typedef long long LL;
const LL N = 2e5 + 7, INF = 1e18;
struct edge { LL v, w; };
vector<edge> e[N];
LL dis[N];
bool used[N];
LL n, m, b;

inline void Dijkstra(int s) {
    for (int i = 1; i <= n; ++i) { dis[i] = INF; }
    // 所有点最短路径初始时要置无穷大
    dis[s] = 0;// 起点到自己的最短路为0
    for (int i = 1; i <= n; ++i) {
        LL u = 0, now = LONG_LONG_MAX;
        // now用来记录当前T中找到的最短路最小的点
        for (int j = 1; j <= n; ++j) {
            if (!used[j] && dis[j] < now) {
            // 如果在集合T中且其最短路长比之前找到的还小就更新
                u = j; 
                now = dis[j];
            }
        }
        used[u] = true;// 放入S集合
        for (auto it : e[u]) {// 对出边进行松弛
            auto v = it.v, w = it.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
            }
        }
    }
    return;
}

这样做的时间复杂度是 \(O(n^2)\)，比刚刚有了很大的提升，但当我们打开一道题，发现数据可能随随便便就超过了 \(10^5\)，\(O(n^2)\) 显然是过不去的，所以我们考虑对其用优先队列进行堆优化。我们发现，在暴力做法中，我们每次都要遍历 \(1\) ~ \(n\) 去寻找集合 \(T\) 中最短路最小的那个点，那么我们就想能不能每次直接从 \(T\) 中拿出最短路最小的点。我们考虑每次从堆顶取出一个点，然后判断这个点是否在集合 \(T\) 中，如果不在那么扔掉再取下一个，否则就进行松弛，成功松弛后 \(u\) 就光荣完成了它的使命，扔进 \(S\) 集合中，而 \(v\) 就入队排序等待后面把它取出。这样重复直到队列为空，我们也就更新完了所有的点，下面是具体实现：

typedef long long LL;
typedef pair<LL, LL> PII;
const LL N = 2e5 + 7, INF = 1e18;
struct edge { LL v, w; };
vector<edge> e[N];
priority_queue<PII, vector<PII>, greater<PII> > q;
LL n, m, b;
LL dis[N];
bool used[N];

inline void Dijkstra(int s) {
    for (int i = 1; i <= n; ++i) { dis[i] = INF; }
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        auto t = q.top(); q.pop();
        // 按照dis排序，每次取出堆顶的点
        LL u = t.second;
        if (used[u]) { continue; }
        // 如果在S集合中就扔掉不管
        used[u] = true;
        // u完成使命放入S集合中
        for (auto it : e[u]) {
            LL v = it.v, w = it.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
                // 成功松弛就扔进队列里
            }
        }
    }
    return;
}

队列中元素的个数是 \(O(m)\) 个，那么维护堆的时间复杂度就是 \(O(logm)\)，我们对每个点都更新一次，所以优化后的时间复杂度是 \(O(mlogm)\)。

我们发现，\(\operatorname{Dijkstra}\) 算法虽然很好用，但是在遇到负边权的时候，每次松弛都会选到负的那条边，因为这样显然更小。松弛后，开始在 \(T\) 中寻找下一个点，结果我们发现最小边权的点变成了上次松弛的 \(v\)，我们又松弛 \(v\)，再下一次又找到了第一次的 \(u\)。结果最后我们在负边相连的两个点间反复横跳，这个算法就寄了，这就是为什么 \(\operatorname{Dijkstra}\) 处理的是非负权图单源最短路。那么遇到负权难道我们就得牺牲时间去用 \(\operatorname{Floyd}\) 了么？显然不是，我们还有其它算法。

\(\operatorname{Bellman-Ford}\) （带负权单源最短路）

\(\operatorname{Bellman-Ford}\) 寻找最短路的方法也是通过和刚刚一样的松弛操作，它每次对所有点都松弛一次，直到松弛到无法松弛为止。一个图内单源最短路的数量最多为 \(n-1\)，这个结论很平凡。所以松弛操作肯定也是最多执行 \(n-1\) 次，那么如果执行多了说明什么？显然是说明有一个负权边使得那两个点开始左右横跳了，那么就判断出了负环。请注意，从 \(s\) 点出发没有找到负环并不能说明图中没有负环，只能说明 \(s\) 点出发抵达的点和边构成的子图中没有负环。想要判断一个图中有没有负环，需要建立一个超级源点，这个源点和图上每一个点都有一条边且边权均为 \(0\)，以超级源点为源点跑 \(\operatorname{Bellman-Ford}\) 就一定可以判断出有没有负环。下面是 \(\operatorname{Bellman-Ford}\) 的具体实现：

typedef long long LL;
const LL N = 2e5 + 7, INF = 1e18;
struct edge { LL v, w; };
vector<edge> e[N];
LL n, m, b;
LL dis[N];

inline bool Bellman_Ford(int s) {
    for (int i = 1; i <= n; ++i) { dis[i] = INF; }
    dis[s] = 0;
    bool flag; 
    // flag用来判断循环时有没有进行松弛
    for (int i = 1; i <= n; ++i) {
        flag = false;
        for (int u = 1; u <= n; ++u) {
            for (auto it : e[u]) {
                auto v = it.v, w = it.w;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    flag = true;
                    // 松弛后打上标记
                }
            }
        }
        if (!flag) { break; }
        // 如果没有松弛说明所有路径更新完毕，可以直接结束
    }
    // n轮松弛后如果仍然能进行松弛，说明一定存在负环
    return flag;
}

最多进行 \(n\) 次松弛操作，每轮操作最多进行 \(m\) 次松弛，所以 \(\operatorname{Bellman-Ford}\) 的时间复杂度为 \(O(nm)\)，数据大的题也是过不去的，所以需要对其进行优化，于是就有了一个人们耳熟能详的算法：\(\operatorname{SPFA}\) 算法。

\(\operatorname{SPFA}\) 的主要思路就是在 \(\operatorname{Bellman-Ford}\) 的基础上，用队列进行优化。我们每次松弛的时候，真正起到实际作用的操作其实只有当 \(u\) 为源点或上次被松弛过，这次的松弛操作才有意义，所以我们把每次松弛的点都扔进队列里，只从队列中取出点来松弛就可以降低时间复杂度。但是请注意，这是一个假算法！诶，那这很奇怪啊，为什么广为人知，受人追捧的可爱的 \(\operatorname{SPFA}\) 会是一个假算法呢？因为我们用优先队列，并不是忽略或者对哪个点不进行松弛，而是改变了松弛的顺序从而达到优化目的，那么如果遇到刻意构造的数据，就可以轻轻松松将 \(\operatorname{SPFA}\) 卡到 \(O(nm)\) 从而让你的程序寄掉。这是某一年国赛带给全体 \(OIer\) 的惨痛教训，所以在没有负环的情况下，尽量不要使用 \(\operatorname{SPFA}\)。下面给出参考代码：

typedef long long LL;
const LL N = 1e6 + 7, INF = 1e18;
struct edge { LL v, w; };
vector<edge> e[N];
queue<int> q;
LL n, m, b;
LL dis[N], cnt[N];
bool used[N];

inline bool SPFA(int s) {
    for (int i = 1; i <= n; ++i) { dis[i] = INF; }
    dis[s] = 0;
    used[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        used[u] = false;
        for (auto it : e[u]) {
            auto v = it.v, w = it.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) { return false; }
                if (!used[v]) { 
                    q.push(v);
                    used[v] = true; 
                }
            }
        }
    }
    return true;
}

说了这么多了让我们来理一理，我们最开始因为 \(\operatorname{Floyd}\) 算法求全源最短路对单源最短路的问题又浪费，所以学习了 \(\operatorname{Dijkstra}\)，又因为其无法处理负权学习了 \(\operatorname{Bellman-Ford}\)。那么，我们需要考虑这样一个问题：如果我们要处理全源最短路，但是数据范围又比较大该怎么办呢？我们是不是可以跑 \(n\) 遍 \(\operatorname{Dijkstra}\)，这样复杂度也不是很高，但碰到负权就寄了，所以就有了另外一个算法。

\(\operatorname{Johnson}\)（全源最短路）

\(\operatorname{Johnson}\) 可以说是前面算法的大杂烩了，\(\operatorname{Dijkstra}\) 和 \(\operatorname{Bellman-Ford}\) 揉在一起再跑。如何处理负环呢，我们首先建立一个超级源点，也就是传说中的 \(0\) 号点，前面已经说过了不再赘述。建立好了以后以这个超级源点为源点跑 \(SPFA\)，其中 \(0\) 号点到 \(i\) 号点的最短路记为 \(newdis_i\)。接下来对于边 \((u,v)=w\)，将其边权设置为 \(w + newdis_u - newdis_v\)，然后再跑 \(n\) 遍 \(\operatorname{Dijkstra}\)，每次求出的 \(dis+newdis_v-newdis_u\) 就是答案了。这种做法的正确性在于从 \(s\) 到 \(t\) 的最短路径长度的势能是没有变的，具体证明见下面这篇博客：正确性证明。下面是参考代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#define LL long long
#define PII pair<LL, LL>
#define clear(cc) memset(cc, 0, sizeof(cc))
using namespace std;

namespace SHAWN {
    const LL N = 6e3 + 7, INF = 1e9;
    struct edge { LL v, w; };
    vector<edge> e[N];
    LL n, m;
    LL dis[N], newdis[N];
    int cnt[N];
    bool used[N];

    inline bool SPFA(int s) {
        queue<int> sq;
        for (int i = 1; i <= n; ++i) { newdis[i] = INF; }
        clear(used);
        newdis[s] = 0;
        used[s] = true;
        sq.push(s);
        while (!sq.empty()) {
            int u = sq.front(); sq.pop();
            used[u] = false;
            for (auto it : e[u]) {
                LL v = it.v, w = it.w;
                if (newdis[v] > newdis[u] + w) {
                    newdis[v] = newdis[u] + w;
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] > n) { return false; }
                    // 注意这里因为插入了超级源点，所以要多跑一轮，>=要变成>
                    if (!used[v]) {
                        sq.push(v);
                        used[v] = true;
                    } 
                }
            }
        }
        return true;
    }

    inline void Dijkstra(int s) {
        priority_queue<PII, vector<PII>, greater<PII> > q;
        for (int i = 1; i <= n; ++i) { dis[i] = INF; }
        clear(used);
        dis[s] = 0;
        q.push({0,s});
        while (!q.empty()) {
            auto t = q.top(); q.pop();
            int u = t.second;
            if (used[u]) { continue; }
            used[u] = true;
            for (auto it : e[u]) {
                LL v = it.v, w = it.w;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    q.push({dis[v], v});
                }
            }
        }
        return;
    }
    
    int work()
    {
        cin >> n >> m;
        for (int i = 1, x, y, z; i <= m; ++i) {
            cin >> x >> y >> z;
            e[x].push_back({y, z});
        }
        for (int i = 1; i <= n; ++i) { e[0].push_back({i, 0}); }
        // 建立超级源点
        if (!SPFA(0)) { cout << "-1\n"; return 0;}
        // 先跑SPFA预处理边权
        for (int u = 1; u <= n; ++u) {
            for (int i = 0; i < e[u].size(); ++i) {
                e[u][i].w += newdis[u] - newdis[e[u][i].v];
            }
        }
        // 更改每条边的边权
        for (int i = 1; i <= n; ++i) {
            Dijkstra(i);// 跑n遍Dijkstra就做完了
            LL ans = 0;
            for (int j = 1; j <= n; ++j) {
                if (dis[j] == INF) { ans += j * INF; }
                else  { ans += j * (dis[j] + newdis[j] - newdis[i]); }
            }
            cout << ans << '\n';
        }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

这样的时间复杂度是 \(O(nmlogm)\)，相比 \(\operatorname{Floyd}\) 还是非常优化的。

总结

想要求单源最短路，可以选择 \(\operatorname{Dijkstra}\) 或 \(\operatorname{Bellman-Ford(SPFA)}\)，时间复杂度分别为 \(O(mlogm)\) 和 \(O(nm)\)，前者只能处理非负权图，而后者可以处理带负权图。想要求全源最短路，可以选择 \(\operatorname{Floyd}\) 或 \(\operatorname{Johnson}\)，时间复杂度分别为 \(O(n^3)\) 和 \(O(nmlogm)\)，二者均可以处理带负权图。也就是说除了 \(\operatorname{Dijkstra}\)，其余的三个算法均可以处理带负权图以及判断负环。比赛时尽量使用 \(\operatorname{Dijkstra}\) 和 \(\operatorname{Johnson}\)，不到迫不得已尽量不要用剩下两种，否则很容易被卡。

以上就是全部内容，如有错误欢迎各位大佬指正。

参考文献：

OI-Wiki 最短路

[洛谷日报#242]Johnson 全源最短路径算法学习笔记

《算法导论（第3版）》

标签：总结,松弛,int,短路,operatorname,LL,dis
From： https://www.cnblogs.com/NightmareAlita/p/shortest_pass_summary.html

相关文章

  • 集训总结
    Day1题单栈单调栈单调队列并查集带权并查集Day2题单树状数组单点加、区间查区间加、单点查区间加、区间查（推导）二维树状数组（推导）树状数组求逆序对WrittenwithStackEdit.......
  • 历时数月钻研推流/对比各种流媒体服务程序/PK总结
    1前言大量测试下来，网页显示视频流实时性从高到低依次是webrtc>ws-flv>flv>hls。播放器打开rtsp/rtmp视频流实时性由具体的播放器控制，比如缓存大小和缓存时间，是否音视频同步等。由于flv拉流同源地址最大支持6路同时播放，所以要想实时性高而且网页播放支持多路就选择ws-fl......
  • 约数总结
    试除法求约数方法1-试除所有数算法原理假设p是x的一个约数，那么x/p一定也是它的约数，所以只需枚举2到$\sqrt[2]{n}$的约数，并且可以直接通过运算获得$\sqrt[2]{n}$之后对应的那个约数时间复杂度$O(\sqrt{n})$代码实现#include<iostream>#include<algorithm>#include<......
  • 约数总结
    试除法求约数方法1-试除所有数算法原理假设p是x的一个约数，那么x/p一定也是它的约数，所以只需枚举2到$\sqrt[2]{n}$的约数，并且可以直接通过运算获得$\sqrt[2]{n}$之后对应的那个约数时间复杂度$O(\sqrt{n})$代码实现#include<iostream>#include<algorithm>#include<......
  • 第五周总结
    这周把mapreduce的课程学习完毕了主要练习了mapreduce里面基本的wordcount操作，切片分区操作，排序方法，outputformat的运行流程，etl数据过滤的方法，文件压缩在mapreduce里面的执行方法。最后还看了yarn的基本概念和操作流程。......
  • 20230816巴蜀暑期集训测试总结
    T1这题一看就很难实现，事实也确实是这样，考场想了半个多小时没有思路，打完暴力就跳了。这道题的正解技巧和思维性很强，不是很套路，只是融合了一些线段树区间操作的思想。感觉......怎么会评蓝呢？这T4一道紫题都明显比T1好做啊！关键T1的考场通过率竟然最高!大概思路就是，变化会形......
  • 2016考研英语：考研作文重要词组总结
    2016考研英语：考研作文重要词组总结 2015-06-11 北京世纪高教编辑部  英语考研写作如果记住一些常用谚语和词组，一定能快速提高作文分数，下面总结的这些谚语及词组希望能助到大家取得好成绩。 一.写作常用谚语1.A friend in need is a friend indeed. ......
  • 8.14总结
    总结题外话：方舟题打得这么烂活该保底t1比赛时阿能和德狗看反，暴毙100（样例太水&赌一把t2想到线段树优化建边+拓扑但是一根筋没有建虚点，也没有将每一个区间去除特殊点变成几个小区间所以在拓扑时的入度就寄飞了t3正经50就差一个线段树优化查询t4毒瘤题目详情请见神秘代码......
  • Spring源码学习笔记13——总结篇, 从IOC到AOP
    系列文章目录和关于我零丶序言在《Spring源码学习笔记12——总结篇,IOC，Bean的生命周期，三大扩展点》中，我们总结了SpringIOC部分的知识，为了更好的给群里的伙伴们分享SpringAOP的知识，遂有了这篇文章，这篇文章将从IOC聊到AOP，其中IOC不会那么细致，重点还是在AOP。一丶引入1.AOP概述......
  • 21硬件总结
    应组长要求，为以后硬件留下知识，避免硬件出现几乎从零开始的局面，本人水平而且文笔有限，只能告诉一些经验之谈，知识相对来说我只是菜狗，希望一届比一届进步吧。首先，就规范来说，对于实验室，是非常必要的，你的原理图，PCB不仅仅你一个人看，你要给你的队友，其他硬件，师弟或者“师妹”看，画......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99