单源最短路径

                     

贡献者: 有机物

预备知识 树与图的深度优先搜索

   单源最短路径问题,为给定一张有向图 $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$ 步也成立。

图
图 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$。


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利