鄂抱特儿最短路

Bertha 。 2021-10-30 06:06 158阅读 0赞

最短路啊， 真是个好东西

例 : 洛谷[p3371][] [p4779 ][p4779]

1.floyed算法

时间复杂度：O(n^3)

利用动态规划的思想每次枚举中转点来更新最短路

便于理解代码简洁。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int N = 5055;
    int mp[N][N], n, m, t;
    void floyed() {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                for(int k = 1; k <= n; k++)
                    if(i != j && mp[i][j] > mp[i][k] + mp[k][j])
                        mp[i][j] = mp[i][k] + mp[k][j];
    }
    int main () {
        scanf("%d%d%d", &n, &m, &t);
        memset(mp, 0x3f3f3f3f, sizeof(mp));
        for(int i = 1; i <= m; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            mp[x][y] = mp[y][x] = z;
        }
        floyed();
        while(t--) {
            int x;
            scanf("%d", &x);
            for(int i = 1; i <= n; i++)
                if(mp[x][i] != 0x3f3f3f3f)
                    printf("%d ", mp[x][i]);
                    else printf("0 ");
            printf("\n");
        }
        return 0;
    }

floyed

2.dijkstra算法

[参考博客][Link 1]

时间复杂度： O(n^2);加入堆优化之后是O((n + m)logn);

不能处理负边

是利用贪心的思想， 把所有的点分为两类第一类是已经计算好最短路的白点， 另一类是未计算好的蓝点， 然后每次寻找一个dis值最小的蓝点， 把她变为白点，然后再用她来更新与她相连的边，重复此过程直至所有的边都已经确定好答案， 即全部点变为白点。

未加堆优化的朴素代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int N = 500007;
    int head[N], cnt, n, m, s;
    long long dis[N];
    bool vis[N];
    struct node {
        int next, to;
        long long w;
    }e[N];
    void add(int x, int y, long long z) {
        e[++cnt].next = head[x];
        e[cnt].to = y;
        e[cnt].w = z;
        head[x] = cnt;
    } 
    void dijkstra(int s) {
        for(int i = 1; i <= n; i++) dis[i] = 2147483647; 
        dis[s] = 0;
        for(int i = 1; i <= n; i++) {
            int k = 1, maxn = 2147483647;
            for(int j = 1; j <= n; j++)
                if(!vis[j] && dis[j] <= maxn)
                    k = j, maxn = dis[j];
            vis[k] = 1;
            for(int j = head[k]; j; j = e[j].next) 
                if(dis[e[j].to] > dis[k] + e[j].w)
                    dis[e[j].to] = dis[k] + e[j].w;
        }
    }
    int main () {
        scanf("%d%d%d", &n, &m, &s);
        for(int i = 1; i <= m; i++) {
            int x, y;
            long long z;
            scanf("%d%d%lld", &x, &y, &z);
            add(x, y, z);
        }
        dijkstra(s);
        for(int i = 1; i <= n; i++)
            printf("%lld ", dis[i]);
        return 0;
    }

朴素 迪杰

加入堆优化的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int N = 1010001;
    int n, m, s, cnt, head[N], dis[N];
    bool vis[N];
    struct node{
        int next, to, w;
    }e[N];
    int read() {
        int s = 0, w = 1;
        char ch = getchar();
        while(!isdigit(ch)){
         if(ch == '-') w = -1;ch = getchar();}
        while(isdigit(ch)){s = s * 10 + ch - '0';ch = getchar();}
        return s * w;
    }
    void add(int x, int y, int z) {
        e[++cnt].next = head[x];
        e[cnt].to = y;
        e[cnt].w = z;
        head[x] = cnt;
    }
    struct Node {
        int u, v;
        bool operator<(const Node &b) const {
            return u > b.u;
        }
    };
    void dijikstra(int s) {
        priority_queue <Node> q;
        memset(dis, 0x3f3f3f3f, sizeof(dis));
        dis[s] = 0;
        Node o;
        o.u = 0;
        o.v = s;
        q.push(o);
        while(!q.empty()) {
            int u = q.top().v;
            int d = q.top().u;
            q.pop();
            if(d != dis[u])continue;
            for(int i = head[u]; i; i = e[i].next) {
                int v = e[i].to;
                int w = e[i].w;
                if(dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    Node p;
                    p.u = dis[v], p.v = v;
                    q.push(p);
                }
            }
        }
    }
    int main () {
        n = read();
        m = read();
        s = read();
        while(m--) {
            int x, y, z;
            x = read();
            y = read();
            z = read();
            add (x, y, z);
        }
        dijikstra(s);
        for(int i = 1; i <= n; i++)
            printf("%d ", dis[i]);
        return 0; 
    }

堆优化 迪杰

我太笨了， 关于重载运算符那里， 死活搞不明白， 生生把一枚可爱的学长：此处省略一千字

所以现在大概是明白了就是比较自身与u的大小就和之前写的cmp函数差不多

3.spfa算法

时间复杂度是O(nm) = O(ke)为平均入队次数， 一般不会超过2

很容易被卡， 我也不知道为什么，所以慎用

读取队头并将与其相连的点更新最小值， 对于与其相邻的点， 若是还没有在队列中则让其入队， 循环直至队列为空

但是弱化版并没有卡spfa

另外

spfa还可以用来判断负环， 若一个点入队超过n次即有负环。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <queue>
    #define N 500005
    #define inf 2147483647
    using namespace std;
    int n, m, s, cnt;
    int dis[N], vis[N], head[N];
    struct node {
        int next, to, w;
    }tr[N];
    void add (int x, int y, int z) {
        tr[++cnt].to = y;
        tr[cnt].next = head[x];
        tr[cnt].w = z;
        head[x] = cnt;
    }
    void spfa () {
        queue<int> q;
        for (int i = 1; i <= n; i++) 
            dis[i] = inf;
        vis[s] = 1;
        q.push(s);
        dis[s] = 0;
        while (!q.empty()) {
            int he = q.front();
            q.pop();
            vis[he] = 0;
            for (int i = head[he]; i ;i = tr[i].next) {
                if (dis[tr[i].to] > dis[he] + tr[i].w) {
                    dis[tr[i].to] = dis[he] + tr[i].w;
                    if (!vis[tr[i].to]) {
                        vis[tr[i].to] = 1;
                        q.push(tr[i].to);
                    }
                }
            }
        }
    }
    int main () {
        scanf ("%d%d%d", &n, &m, &s);
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            scanf ("%d%d%d", &a, &b, &c);
            add (a, b, c);
        }
        spfa ();
        for (int i = 1; i <= n; i++) 
            if (s == i) printf ("0 ");
            else printf ("%d ", dis[i]);
        return 0;
    }

spfa

真的很感谢[SovietPower][]非常耐心的给我讲！**Orz**

转载于:https://www.cnblogs.com/yanxiujie/p/11360811.html

[p3371]: https://www.luogu.org/problem/P3371
[p4779]: https://www.luogu.org/problem/P4779
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/ac35ff2936ed4ff5844cda74cff421de.png
[Link 1]: https://www.cnblogs.com/little-sun0331/p/9484730.html
[SovietPower]: https://www.cnblogs.com/SovietPower/