单源最短路径

贡献者： 有机物

　　 单源最短路径问题，为给定一张有向图 $G = (V, E)$，$V$ 是点集，$E$ 是边集，$|V|= n$，$|E| = m$，求给定的源点（起点）$s \in V$ 到每个结点 $v \in V$ 的最短路径。$(x, y, w)$ 表示有一条从结点 $x$ 指向结点 $y$ 的有向边，边权为 $w$。

1. Dijkstra 算法

　　 dist[i] 表示从起点 $s$ 到结点 $i$ 的实际最短路径的长度（这条路径的权值之和）。

　　 $\delta(u)$ 表示从起点 $s$ 到结点 $u$ 的估计最短路径长度。任意时刻都存在 $dist[u] \leq \delta(u)$。 Dijkstra 算法是一种求解没有负权边的图中的单源最短路问题。将所有结点划分为两个集合，$S$ 集合存储当前已经确定了最短路的结点，$T$ 集合存储当前还未确定最短路的结点。

　　 具体做法是：

1. 初始化所有点的 dist 距离为正无穷，起点的距离为 $0$（dist[S] = 0）。
2. 每次从 $T$ 集合中选出一条 dist 值最小的结点 $t$，并把 $t$ 结点加入 $S$ 集合中。
3. 用 $t$ 更新其他结点。
4. 重复 $2 \sim 3$ 步骤，直到所有点都被加入 $S$ 集合。

　　 朴素 Dijkstra 算法的时间复杂度为 $\mathcal{O}(n \times m)$，使用二叉堆可以使操作 $2$ 的时间复杂度从 $\mathcal{O}(n \times m)$ 的时间复杂度优化到 $\mathcal{O}(\log_2 n)$。每更新一条边 $(x, y)$，就把 $y$ 这个结点和 dist[y] 值插入到二叉堆中。每次找最小值直接取堆顶即可。每次取堆顶时判断堆顶是不是已经被访问过了，如果被访问过了，直接忽略这次操作，否则会重复更新，导致影响时间复杂度。所以堆优化版 Dijkstra 的时间复杂度为 $\mathcal{O}(m \log_2 n)$。

Dijkstra 算法正确性证明：

　　 1. 参考算法导论中的反证法

　　 要证明在算法结束时，每个点的实际最短距离等于估计最短距离，即证明的是对于每个结点 $u \in V$，当结点 $u$ 第一次加入到 $S$ 集合时，$dist[u] =\delta(u)$，也就是 dist[u] 必然满足已经是起点到 $u$ 的最短距离。

　　 初始化：$S = \varnothing$，方程显然成立，得证。

　　 接下来使用反证法证明此结论，假设结点 $u$ 是第一次加入 $S$ 集合时使得 $dist[u] \neq \delta(u)$，因为 $s$ 结点是第一次加入 $S$ 集合中的结点，所以有 $dist[s] = \delta(s) = 0$，因为 $s$ 结点是第一个加入 $S$ 结点中的结点，所以将 $u$ 结点加入 $S$ 集合之前，必定有 $S \neq \varnothing$。此时一定有一条从 $s$ 结点到 $u$ 结点的路径，否则 $dist[u] = \delta(u) = +\infty$，而这与假设矛盾，所以一定存在一条路径从结点 $s$ 到结点 $u$。

　　 所以这条路径上一定存在一条最短从结点 $s$ 到结点 $u$ 的最短路径 $p$。 将 $p$ 分解为：$s \thicksim x \thicksim y \thicksim u$，其中 $y$ 为第一个属于 $T$ 集合中的点，$x$ 为 $y$ 的前驱结点。有可能存在 $s = x$ 或 $y = u$ 的情况。

　　 因为结点 $u$ 是第一次加入 $S$ 集合时不满足 $dist[u] \neq \delta(u)$ 的结点，所以在之前所以的结点都满足实际最短路径等于估计最短路径，所以在将 $x$ 结点加入到 $S$ 集合时，满足 $dist[x] = \delta(x)$。此时 $x$ 结点会更新其他结点，所以在将 $u$ 加入到 $S$ 集合时，$dist[y] = \delta(y)$。

　　 因为结点 $y$ 是结点 $u$ 的前面的一个结点，所以存在 $\delta(y) \leq \delta(u)$。所以 $dist[y] = \delta(y) \leq \delta(u) \leq dist[u]$。又因为结点 $u$ 是算法在 $T$ 集合中选择的第一个点，所以有 dist[u] <= dist[y]。所以上面的不等式其实都为等式，所以 $\delta(u) = dist[u]$ 成立，这与假设矛盾，所以证明得证。

　　 2. 使用数学归纳法证明

　　 证明在第 $k$ 步算法选择的不在 $S$ 集合中距离 $S$ 集合最近的点，它在被加入 $S$ 集合时，它的路径就是最短路径。

　　 首先当 $k = 1$ 时，$S$ 集合中只有源点 $s$，它的最短路径已经被确定，就是 $0$。

　　 假设对 $k$ 成立，那么对第 $k + 1$ 步也成立。

　　 令 $d_i = dist[i]$，$w$ 为边权。

　　 第 $k$ 步算法选择的点为 $u$，它的最短路径已经被确定，并且加入到了 $S$ 集合中。考虑第 $k + 1$ 步算法选择了 $u \to v$ 这条边的 $v$ 结点。若存在另一条路径 $s \to y \to v$，即证：$d_v \leq d_y + w(y \to v)$。

　　 反证法：假设算法第 $k + 1$ 选择了 $y$，那么有：$d_v > d_y + w(y \to v)$，看看有没有什么矛盾发生。因为有 $d_v > d_y + w(y \to v)$，所以不难看出：$d_v > d_y$，因为第 $k$ 步算法选择了 $u$ 这个点，所以在图上可以看出 $d_y \geq d_u$，因为：$d_v > d_y$，并且 $d_v = d_u + w(u \to v)$，所以有 $d_u + w(u \to v) > d_y$，又因为 $d_y \geq d_u$，所以 $d_u + w(u \to v) > d_u$。可以从图中看出，$d_u$ 无论如何也不可能严格大于 $d_v$，所以假设不成立，所以 $d_v \leq d_y + w(y \to v)$ 式成立。

　　 证毕。

　　 C++ 代码：

　　 朴素版 Dijkstra

const int N = 1e5 + 10, M = 510, INF = 0x3f3f3f3f;
int n, m, dist[N], st[N], g[M][M]; // st 为 true 表示在 S 集合，反之不在

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);  // 初始化距离
    dist[1] = 0;
    
    for (int i = 0; i < n - 1; i ++ ) // 迭代 n - 1 次
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j; // t 为 不在 S 集合中距离最短的点
        
        st[t] = true; // 加入 S 集合
        
        for (int j = 1; j <= n; j ++ ) // 更新
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    // 求 1 号点到 n 号点的最短距离
    return dist[n];
}

int main()
{
    cin >> n >> m;
    
    // 稠密图用邻接矩阵存图
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < m; i ++ ) 
    {
        int a, b, c;
        cin >> a >> b >> c;
        // 因为图中可能有重边，所以只保留权值小的边
        g[a][b] = min(g[a][b], c);
    }
    
    // 输出邻接矩阵，没有边的地方初始化为正无穷
    for (int i = 1; i <= 4; i ++ ) {
        for (int j = 1; j <= 4; j ++ )
            printf("%10d ", g[i][j]);
        cout << endl;
    }
    
    int t = dijkstra();
    if (t == INF) cout << -1 << endl; 
    else cout << t << endl;
    
    return 0;
}

　　 堆优化版 Dijkstra

const int N = 1e6 + 10, INF = 0x3f3f3f3f;
typedef pair<int, int> PII; // first 存储距离，second 存储结点编号
priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
int n, m, dist[N], st[N], h[N], e[N], w[N], ne[N], idx; // 稀疏图用邻接表存图

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    heap.push({0, 1});  // 把起点加入到优先队列中
    
    while (heap.size())
    {
        auto t = heap.top(); // 取出堆顶
        heap.pop();
        
        int ver = t.second;
        if (st[ver]) continue;  // 如果访问过就不重复访问
        st[ver] = true;
        
        for (int i = h[ver]; ~i; 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});
            }
        }
    }
    
    // 求 1 号点到 n 号点的最短距离
    return dist[n];
}

2. Bellman-Ford 算法与 SPFA 算法

　　 Bellman-Ford 算法可以求解带有负权边的单源最短路径。

　　 Bellman-Ford 算法的步骤非常简单，就是迭代 $n - 1$ 次，依次扫描每条边，如果边能够被更新的，就更新一下每条边。具体的：对于每条边 $(x, y, w)$，如果 $dist[y] > dist[x] + w$，则用 $dist[x] + w$ 更新 $dist[x]$。这种更新方法被称为松弛操作。

　　 迭代结束之后，如果每条边都满足 $dist[y] \leq dist[x] + w$，则所有边都满足三角不等式性质。

　　 Bellman-Ford 算法的时间复杂度为 $\mathcal{O}(nm)$。

　　 队列优化版的 Bellman-Ford 算法在国内被称为 SPFA 算法。SPFA 的优化思路是对上面的松弛操作做优化，因为不一定所有的边都会被松弛，只有当前结点的出边变小了，当前结点才有可能被更新。

　　 SPFA 算法的流程为：

1. 建立一个队列，最初把起点入队
2. 当队列非空，取出队头并弹出队头
3. 更新队头的所有出边 $(t, y, w)$
4. 如果队头的出边没有入队过，则把队头的出边入队
5. 重复 $2 \sim 4$，直到队列为空。

　　 SPFA 算法的期望时间复杂度为 $\mathcal{O}(m)$，但最坏情况会被卡到 $\mathcal{O}(nm)$。

　　 C++ 代码： SPFA

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, dist[N], st[N], q[N], h[N], e[N], w[N], ne[N], idx;

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int hh = 0, tt = 0; // 循环队列
    q[tt ++ ] = 1;
    st[1] = true;
    
    while (hh <= tt)
    {
        auto t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

　　 Bellman-Ford 算法与 SPFA 算法一个很好的应用就是可以判断一个图中存不存在负环（一张图中存在一个环，权值之和为负数）。一般判断负环的算法选择 SPFA，因为 SPFA 的效率要远远大于 Bellman-Ford 算法。

　　 SPFA 算法判断负环的方法有两种，分别为：

1. 记录每个结点入队次数，若有某个结点入队次数大于等于结点总数，说明存在负环。
2. 记录每个结点到 $1$ 号结点的最短路径包含的边数，若某个结点到 $1$ 号结点的最短路径包含的边数大于等于结点总数，也说明图中存在负环。

　　 方法 $1$ 的原理：本质是 Bellman-Ford 算法，若经过了 $n$ 轮迭代，还有结点可以被更新的话，说明存在负环。对于 SPFA 来说，每个结点被更新一次就入队一次，如果一个结点入队的次数大于等于 $n$ 次，那么这个结点就被更新了大于等于 $n$ 次。一个结点每更新一次，这个结点的最短路径的距离就会加 $1$，那么一个结点更新 $n$ 次，说明这个结点的最短路径的距离的长度就等于 $n$，显然这条最短路径的结点个数就等于 $n + 1$。图中一共有 $n$ 个点，这个结点的最短路径中包含的结点个数大于等于 $n$ 了，根据抽屉原理，必然有两个一样的结点，说明存在一个环，根据松弛操作，这个环一定是负环。

　　 方法 $2$ 的原理：类似于方法 $1$，原理其实也是抽屉原理，用一个 cnt 数组记录每个点的最短路径包含的边数，每松弛一次，更新一下距离并且更新一下 cnt 数组。如果 cnt[i] >= n，说明图中存在负环。

　　 SPFA 算法判断负环推荐使用第二种，第二种的效率远远高于第一种，对于这样一张图，图中的边权都为负数，且有很多点。第一种方法需要绕环 $n$ 次才能达到一个结点入队的次数大于等于 $n$，而第二种方法则需要绕环 $1$ 次，再走一个结点就能达到一个结点的最短路径包含的边数大于等于 $n$。第一种方法的时间复杂度可以近似的看成 $\mathcal{O}(n^2)$，而第二种的时间复杂度可以近似的看成 $\mathcal{O}(n)$。

　　 判断负环还要注意一种情况，有可能构成负环的结点不与 $1$ 号点联通，那么只把 $1$ 号点加到队列里就不能成功的找到负环。所以一种很实用的方法是最开始将所有点入队，这样就能成功的遍历到所有结点并找到负环。这种方法的一种更好的理解方式就是，设立一个虚拟源点，从虚拟源点向所有点连一条边权是 $0$ 的边。然后初始化是把虚拟源点加入队列，然后第一次迭代是把虚拟源点可以到达的点全部加入队列。所以最开始将所有点加入队列等价于在图中建立一个虚拟源点。

　　 还需注意的一点是 SPFA 算法判断负环不需要初始化 dist 数组为正无穷，初始化任意值都没问题，因为如果图中存在负环，松弛操作一定会执行，所以所以 dist 的值初始化任意值都没问题。这里的正无穷（0x3f3f3f3f）严格意义来讲其实是有限值，为 $1061109567$。

const int N = 2010, M = 1e4 + 10, INF = 0x3f3f3f3f; // N 结点数量
int n, m, dist[N], st[N], cnt[N], q[N], h[N], e[M], w[M], ne[M], idx;

bool spfa()
{
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, false, sizeof st);

    int hh = 0, tt = 0; // 循环队列
    for (int i = 1; i <= n; i ++ )
    {
        q[tt ++ ] = i;
        st[i] = true;
    }
    
    int count = 0; // 计数器
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; 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 ( ++ count > N) return true;  // trick
                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;    
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

　　 实际运用中 SPFA 的效率其实不是那么好，这里有个经验上的做法，如果 SPFA 的效率很低的时候，就认为有负环。这里的技巧是：当所有点的总共入队次数超过一个定值的时候，就认为有负环。定值经验上取 $2 \times n$ 或 $3 \times n$。