最短路最最最基础

最短路最最最基础

九月 01, 2021

categories: 学习笔记

图论基础

最短路

image-20210715160552989

性质

对于边权为正的图，任意两个结点之间的最短路，不会经过重复的结点。

对于边权为正的图，任意两个结点之间的最短路，不会经过重复的边。

对于边权为正的图，任意两个结点之间的最短路，任意一条的结点数不会超过n，边数不会超过n-1。

Floyd 算法

是用来求任意两个结点之间的最短路的。

复杂度比较高，但是常数小，容易实现。（只有三个 for）

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

实现:image-20210715173428802

1
2
3
4
5
6
7
for (k = 1; k <= n; k++) {
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
        f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j]);
        }
    }
}

因为第一维对结果无影响，我们可以发现数组的第一维是可以省略的，于是可以直接改成 f[x][y] = min(f[x][y], f[x][k]+f[k][y])。

证明第一维对结果无影响

我们注意到如果放在一个给定第一维 k 二维数组中，f[i][k] 与 f[k][j] 在某一行和某一列。而 f[i][j] 则是该行和该列的交叉点上的元素。

现在我们需要证明将 f[k][i][j] 直接在原地更改也不会更改它的结果：我们注意到 f[k][i][j] 的涵义是第一维为 k-1 这一行和这一列的所有元素的最小值，包含了 f[k-1][i][j]，那么我在原地进行更改也不会改变最小值的值，因为如果将该三维矩阵压缩为二维，则所求结果 f[i][j] 一开始即为原 f[k-1][i][j] 的值，最后依然会成为该行和该列的最小值。

故可以压缩，压缩后代码如下

1
2
3
4
5
6
7
for (k = 1; k <= n; k++) {
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        }
    }
}

综上时间复杂度是$O(N^3)$ ，空间复杂度是$O(N^2)$ 。

应用

image-20210715201209071

Dijkstra算法

Dijkstra 是个人名（荷兰姓氏）。

IPA:/ˈdikstrɑ/或/ˈdɛikstrɑ/。

这种算法只适用于非负权图，但是时间复杂度非常优秀。

也是用来求单源最短路径的算法。

实现

主要思想是，将结点分成两个集合：已确定最短路长度的，未确定的。

一开始第一个集合里只有S。

然后重复这些操作：

  1. 对那些刚刚被加入第一个集合的结点的所有出边执行松弛操作。
  2. 从第二个集合中，选取一个最短路长度最小的结点，移到第一个集合中。

直到第二个集合为空，算法结束。

时间复杂度：只用分析集合操作， n次 delete-min， n次 decrease-key。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<LL>> Ps;  // 图的邻接矩阵
vector<LL> dist;        // min_len 的运行结果存储位置
// i: 源点在点集中的下标
void min_len(size_t i) {
    using Pair = pair<LL, size_t>;  // pair 的排序是先第一分量后第二分量，
    for (auto &k : dist) k = LLONG_MAX;// 通过这个可以调整它在堆中的位置
    dist[i] = 0;// 初始化 dist
    priority_queue<Pair, vector<Pair>, greater<Pair>> Q;// 初始化小根堆  
    Q.push(Pair(0, i));// 小根堆
    while (!Q.empty()) {
        auto k = Q.top().second;
        Q.pop();
        for (size_t i = 0; i < Ps[k].size(); i++) { // 如果 k 和 i 有边连（这里设置 Ps[k][i] == 0 时无边连接）
            if (Ps[k][i] && dist[k] + Ps[k][i] < dist[i]) {
                // 松弛操作
                dist[i] = dist[k] + Ps[k][i];
                Q.push(Pair(dist[i], i));
            }
        }
    }
}