JZTXT

最短路

发布时间 2023-07-08 21:32:43作者: 我是浣辰啦

概念

  • 单源最短路：给出一点 \(S\) ，求 \(S\) 到所有点的最短路
  • 多源最短路：给出多点 \(S\) ，求 \(S\) 到所有点的最短路
  • 全源最短路：给出所有点 \(S\) ，求 \(S\) 到所有点的最短路

实现

Floyd 算法

Floyd 算法基于 DP 思想，采用邻接矩阵存边

复杂度比较高，但是常数小，容易实现

适用于所有图，不管有向无向，边权正负，但是最短路必须存在。（但是不能有负环）

具体思路：枚举所有的两两点的组合以及每一个组合的“中转点”，再进行松弛操作

设 \(a_{x,y}\) 表示 \(x \to y\) 的最短路径长度

初始化：

\[a_{x,y}=\begin{cases} 0 & x = y \\ \infty &x \not = y \end{cases} \]

在求单源最短路径的时候就会浪费许多空间，但在求多源最短路时，复杂度仍是 $ O(n^{3}) $

代码示例：

inline void Floyd() {
    for (int k = 1; k <= n; ++k) // 枚举中转点
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}

在用 Floyd 转递闭包时，我们可以考虑优化一点点：

在枚举两两的中转点时，我们枚举了很多不连通的点，而这些点是没有贡献的

所以我们可以用 bitset 存边，每次用 _Find_next 寻找下一个联通的点

时间复杂度为 \(O(\dfrac{n^{3}}{k})\)​（k是一个常数）

应用

P6175 无向图的最小环问题

首先其一定是一个简单环

在枚举 \(k_{i}\) 的时候，我们已经得到了前 \(k-1\) 个点的最短路径

f[x][y] 和 \((k,x), (k,y)\)共同构成了环。

所以连接 $ x \to y \to k \to x $ ，我们就得到了一个经过 \(x , y , k\) 的最小环

在 Floyd 的过程中枚举 \(k\) ，计算这个和的最小值即可。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll inf = 1e18;
const int N = 1e2 + 7;

ll dis[N][N], mp[N][N];

ll ans = inf;
int n, m;

inline void init() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                dis[i][j] = mp[i][j] = inf;
}

inline void Floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i < k; ++i)
            for (int j = i + 1; j < k; ++j)
                ans = min(ans, dis[i][j] + mp[i][k] + mp[k][j]);

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dis[j][i] = dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    }
}

signed main() {
    scanf("%d%d", &n, &m);
    init();

    for (int i = 1, u, v; i <= m; ++i) {
    	ll w;
        scanf("%d%d%lld", &u, &v, &w);
        dis[u][v] = dis[v][u] = min(dis[u][v], w);
        mp[u][v] = mp[v][u] = min(mp[u][v], w);
    }
    
    Floyd();

    if (ans == inf)
        printf("No solution.");
    else
        printf("%lld", ans);

    return 0;
}

SPFA 算法

SPFA基于广搜思想，是经过队列优化的 Bellman-Ford 算法

我们用 dis 数组记录源点到图上任意一点距离，其中源点到自身距离为 \(0\) ，到其他点距离为 \(\infty\)

将源点入队，并重复以下步骤：

  1. 队首 \(x\) 出队
  2. 遍历所有以队首为起点的有向边 \(x \to i\) ，若 \(dis_x + w(x,i) < dis_i\) ，则更新 \(dis_i\)
  3. 如果点i不在队列中，则 \(i\) 入队
  4. 若队列为空，跳出循环；否则执行1

但是这么写在有源点可以到达的负环的情况下会T飞

考虑最短路存在的时候。

由于一次松弛操作会使最短路的边数至少 \(+1\) ，而最短路的边数最多为 \(n-1\)。

所以最多执行 次松弛操作，\(n-1\) 即最多循环 \(n-1\) 次。

那么一个点入队次数 \(\geq n\)​ ,就会存在负环，我们就可以退出

如果图是随机的，时间复杂度为 \(O(KE)\)

但是实际上 SPFA 的最坏复杂度是 \(O(VE)\) ，可以构造出卡 SPFA 的数据，让 SPFA 超时。

代码：

inline bool SPFA(int s) {
    memset(dis, inf, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    memset(inque, false, sizeof(inque));
    queue<int> q;
    q.push(s);
    inque[s] = true, dis[s] = 0, cnt[s] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inque[u] = false;

        for (int i = 0, v, w; i < e[u].size(); ++i) {
            v = e[u][i].first, w = e[u][i].second;

            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;

                if (!inque[v]) {
                    q.push(v), inque[v] = true, ++cnt[v];

                    if (cnt[v] >= n)
                        return false; // 有负环
                }
            }
        }
    }

    return true;
}
优化
  • LLL 优化：每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾
  • SLF 优化：每次将入队结点距离和队首比较，如果更大则插入至队尾
  • SLF 带容错：每次将入队结点距离和队首比较，如果比队首大超过一定值则插入至队尾
  • mcfx 优化：定义区间 \([l, r]\) ，当入队点入队次数属于这个区间时从队首插入，反之从队尾插入
  • SLF + swap：每当队列改变时，如果队首距离大于队尾，则交换首尾
    • 这个 SLF 看起来很弱，但却通过了所有 Hack 数据，而且非常难卡
卡 SPFA

首先要清楚卡 SPFA 的原理是让点尽可能多次的入队，反复更新

如果一个点被多个边连着，那么当这些边先依次走向它的时候，这个点就会被调用很多次，然后往下走，于是可以构造一个链套菊花，这样对于菊花的那个点会反复入队很多次，然后往下每次都要走很多次，于是就死了。

另一种卡法是构造一个网格图，行比列小得多，比如 \(10 \times 10^4\) 之类的，然后对于竖着的边权设得很小，横着的边权设的很大，如 \(1\) 和 \(rand() \bmod 10^4 + 10\) 。因为如果在网格图中走错了一次，就会走很多步无用步，于是就死了。

但是每次将进队多次得点放到队首可以优化复杂度

考虑构造这样的边：\((1, i, 2(n - i + 1) + 1), (i, i - 1, 1)\) ，即可

那么结合两种卡法，对于普通的SPFA最好的卡法就是将图构造为一个网格套链套菊花

针对优化的 Hack

  • LLL 优化：向 \(1\) 连一条权值巨大的边
  • SLF 优化：链套菊花
  • SLF带容错：卡 SLF 的做法，并开打大边权总和，最好超过 \(10^{12}\)
  • mcfx 优化：菊花图
  • SLF + swap：与卡 SLF 类似，外挂诱导节点即可

Dijkstra 算法

首先，在这个算法中，有两种点，一种是已经确定最短路径的点（又称为蓝点），一种是尚未确定最短路径的点（又称为白点）。蓝点的最短路径不会再改变

这样为什么就能得出从起点出发所有点的最短路径呢？

首先，所有点都是蓝点，起点到起点的最短路径为 \(0\)

然后要找出一个当前没有到达过的点（白点）中路径最短的点，记为 \(u\) 。将 \(u\) 设为蓝点（确定它的最短路径）。

那为什么当前最短路径最短的白点，可以转化为蓝点呢？

反证法：

如果 \(u\) 的 \(dis\) 值还能更新，考虑从 \(S\) 到它的最短路径，其倒数第二个点，一定是现在的白点（如果它的 \(dis\) 值还能更新，又不是由蓝点更新的，自然就是由白点更新的）。设这个白点为 v，既然 \(u\) 是当前 \(dis\) 最小的，\(dis_{v} > dis_{u}\)，那 \(dis_v + w{v -> u}\) 不可能 \(> dis_{u}\)

万一有负边权呢？

给每条边加上一个数字的做法显然是错误的，如果这样处理，最短路径会极大地受到经过边数的影响。

事实上 Dijkstra 算法只能解决正权图上的最短路问题问题

复杂度分析：外层一个循环，去除最小值一个循环，所以时间复杂度就是 $ O(n^{2}) $

事实上，对于取出当前白点里 \(dis\) 值最小的这一步，我们可以用堆优化 ，时间复杂度降至 $ O(n \log n + m) $

代码：

inline void Dijkstra(int s) {
    memset(dis, inf, sizeof(dis));
    memset(vis, false, sizeof(vis));
    priority_queue<pair<int, int> > q;
    dis[s] = 0, q.push({0, s});

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();

        if (vis[u])
            continue;

        vis[u] = true;

        for (int i = 0, v, w; i < e[u].size(); ++i) {
            v = e[u][i].first, w = e[u][i].second;

            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

另一种写法（取消了 \(vis\) 数组）：

inline void Dijkstra(int s) {
    memset(dis, inf, sizeof(dis));
    priority_queue<pair<int, int> > q;
    dis[s] = 0, q.push({0, s});

    while (!q.empty()) {
        pair<int, int> c = q.top();
        q.pop();

        if (dis[c.second] != -c.first)
            continue;

        int u = c.second;

        for (int i = 0, v, w; i < e[u].size(); ++i) {
            v = e[u][i].first, w = e[u][i].second;

            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
}

Johnson 全源最短路

为了解决 Dijkstra 跑不了负边权的问题，Johnson提出了一种船新的办法。

我们建一个超级源点，所有点与其连一条边权为 \(0\)​ 的边。

先采用 SPFA 算法将每个点与 超级源点的最短路径长度算出来，这里记作 \(h_i\)​ 。

设一条有向边 \(u \to v\) 边权为 \(w\) ，那么将每条边的边权增加 \(h_u-h_v\)​ ，当然，最后统计答案的时候要将其减去，接下来就可以直接跑 Dijkstra了

P5905 【模板】Johnson 全源最短路

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 3e3 + 7;

vector<pair<int, int>> e[N];

int dis[N][N];
int h[N], cnt[N];
bool inque[N], vis[N];

int n, m;

inline void AddEdge(int u, int v, int w) {
	e[u].push_back(make_pair(v, w));
}

inline bool SPFA(int s) {
    memset(h, inf, sizeof(h));
    queue<int> q;
    q.push(s);
    h[s] = 0, inque[s] = true, cnt[s] = 1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inque[u] = false;

        for (int i = 0, v, w; i < e[u].size(); ++i) {
            v = e[u][i].first, w = e[u][i].second;

            if (h[v] > h[u] + w) {
                h[v] = h[u] + w;

                if (!inque[v]) {
                    q.push(v);
                    inque[v] = true;
                    ++cnt[v];

                    if (cnt[v] > n)
                        return false;
                }
            }
        }
    }

    return true;
}

inline void Dijkstra(int *d, int s) {
	memset(vis, false, sizeof(inque));
    priority_queue<pair<int, int> > q;
    d[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();

        if (vis[u])
            continue;

        vis[u] = true;

        for (int i = 0, v, w; i < e[u].size(); ++i) {
            v = e[u][i].first, w = e[u][i].second + h[u] - h[v];

            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push(make_pair(-d[v], v));
            }
        }
    }
}

inline bool Johnson() {
    for (int i = 1; i <= n; ++i)
        AddEdge(0, i, 0);
    
    if (!SPFA(0))
    	return false;

	memset(dis, inf, sizeof(dis));
	
    for (int i = 1; i <= n; ++i)
        Dijkstra(dis[i], i);
    
    return true;
}

signed main() {
    scanf("%d%d", &n, &m);

    for (int i = 1, u, v, w; i <= m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        AddEdge(u, v, w);
    }

    if (!Johnson())
        return puts("-1"), 0;

    for (int i = 1; i <= n; ++i) {
        ll ans = 0;

        for (int j = 1; j <= n; ++j) {
            if (dis[i][j] == inf)
                ans += 1ll * j * 1e9;
            else
                ans += 1ll * j * (dis[i][j] - h[i] + h[j]);
        }

        printf("%lld\n", ans);
    }

    return 0;
}

扩展

最短路图

即求出所有最短路（多条也算）组成的图，往往在求最值时第一关键字为最短路时配合 DP 使用

「ROI 2017 Day 1」前往大都会

首先求出最短路图，那么只要在图上找到平方和最大的路径

这里的最短路图是 DAG， 于是可以按拓扑序设计 DP

设 \(dp_x\) 表示以 \(x\) 为终点的最大权值，枚举上一个换乘点，有

\[f_x = \max_y \{ f_y + (d_x - d_y)^2 \} = d_x^2 + \max_y \{ d_y^2 - 2d_x d_y + f_y \} \]

斜率优化即可，复杂度瓶颈为最短路