算法图算法

带权图最短路径算法与实现

字数统计: 3.8k字   |   阅读时长: 16分
, , ,

摘要: 带权图单源最短路

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们以力扣 743 为模板题来看一下带权图的单源最短路问题的各种算法的原理以及实现。涉及到以下算法：

  • dkijstra 算法，基于数组的实现和基于堆实现
  • bellman ford 算法
  • spfa 算法
  • floyd 算法

$0 最短路径问题

给定带权有向图 $G = (V, E)$ 和权重函数 $w: E \rightarrow \mathbb{R}$，该权重函数将每条边映射到实数值的权重上。

图中的一条路径 $p = (v_{0}, v_{1}, \cdots, v_{k})$ 的权重 $w(p)$ 是构成该路径的所有边的权重之和：

定义从节点 $u$ 到节点 $v$ 的最短路径权重 $\delta(u, v)$ 如下：

从 $u$ 到 $v$ 的最短路径定义为任何一条权重为 $w(p) = \delta(u, v)$ 的从 $u$ 到 $v$ 的路径 $p$。

最短路径的最优子结构

最短路径算法通常依赖最优子结构性质：两个节点之间的一条最短路径包含着其他的最短路径。

最大流的 Edmonds-Karp 算法也依赖这个性质。

我们知道最优子结构是使用动态规划和贪心算法的一个重要的要求。基于最短路径的最优子结构，Dijkstra 算法是贪心算法，Folyd 算法是动态规划算法。

下面我们给出最短路径的最优子结构的定理描述：

给定带权有向图 $G = (V, E)$ 和权重函数 $w: E \rightarrow \mathbb{R}$，设 $p = (v_{0}, v_{1}, \cdots, v_{k})$ 为从节点 $v_{0}$ 到 $v_{k}$ 的一条最短路径，并且对于任意的 $0 \leq i \leq j \leq k$，设 $p_{ij} = (v_{i}, \cdots, v_{j})$ 为路径 $p$ 中从节点 $v_{i}$ 到 $v_{j}$ 的子路径，那么 $p_{ij}$ 为从节点 $v_{i}$ 到 $v_{j}$ 的一条最短路径。

最优子结构的证明

如果将路径 $p$ 分解为 $v_{0}\stackrel{p_{0i}}{\rightarrow}v_{i}\stackrel{p_{ij}}{\rightarrow}v_{j}\stackrel{p_{jk}}{\rightarrow}v_{k}$，则有：

现在假设存在一条从 $v_{i}$ 到 $v_{j}$ 的路径 $p^{‘}_{ij}$，且 $w(p^{‘}_{ij}) < w(p_{ij})$。则 $v_{0}\stackrel{p_{0i}}{\rightarrow}v_{i}\stackrel{p^{‘}_{ij}}{\rightarrow}v_{j}\stackrel{p_{jk}}{\rightarrow}v_{k}$ 是一条从节点 $v_{0}$ 到节点 $v_{k}$ 的权重为 $w(p_{0i}) + w(p_{ij}^{‘}) + w(p_{jk})$ 的路径，而该权重小于 $w(p)$，这与 $p$ 是从 $v_{0}$ 到 $v_{k}$ 的一条最短路径这一假设矛盾。

$1 题目

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

提示：

1
2
3
4
5
6
7
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）

示例 1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

$2 题解

图论的题目一般是 3 步，建图 -> 图论算法 -> 后处理。

本题也是一样的思路：先建邻接表，然后求单源最短路，然后根据找到的各个点的最短路，找到从起始点出发可以到达的最远的距离。

一般比较难的题目难点都是在建图这一步。有的是非常隐晦的图论问题，想不到建图处理，例如 127. 单词接龙；有的是建图过程中 corner case 非常多，很容易漏，例如 444. 序列重建。成功完成建图之后(一般是建邻接表比较多)，之后的图论算法就比较模板化了。

当边的权都相同时，求最短路直接一趟 BFS就可以，典型题目 1091. 二进制矩阵中的最短路径。当边权不同的时候有以下几种。

  • dijkstra 数组实现: $O(E + V^2)$，有贪心思想，不能处理负权
  • dijkstra 堆实现: $O(E\log E)$，有贪心思想，不能处理负权
  • bellman ford: $O(VE)$, 可以处理负权，可以检测负环
  • spfa: $O(VE)$, bellman ford 的优化, 可以处理负权，可以检测负环
  • floyd: $O(V^3)$ 可以把所有点之间的最短路径求出，如果求多源最短路，时间复杂度可摊销

如果没有负权的话，一般使用 dijkstra 最好。

代码框架就是 建立邻接表 -> 单源最短路算法 -> 后处理

单源最短路算法的 5 种算法都是模板，接口如下：

1
2
// g 是建好的邻接表，start 是起始点，N 是节点个数； 返回各个点到 start 的最短路径
vector<int> shortest_path(vector<vector<vector<int> > >& g, int start, int N)；

下面分别以上面的 5 种算法实现该接口。

算法1 : dijkstra

给定一个有向带权图 $G = (V, E)$，其中每条边的权是非负数。指定 $V$ 中的一个点作为源点。要计算从源点到所有其它顶点的最短路径长度。

迪杰斯特拉（Dijkstra）提出按照各个顶点与源点之间路径长度的递增次序，生成源点到各个顶点的最短路径的方法。也就是先求出长度最短的一条路径，然后参照该路径求出长度次短的一条路径，以此类推，直到从源点到其他各个顶点的最短路径全部求出。

该算法的推导过程，正确性证明参考这篇文章 迪杰斯特拉算法，最终的算法流程如下：

以下 (1)(2) 的流程循环 N - 1 次:

  • (1) 从尚未找到最短路径长度，也就是满足 !visited[u] 的节点中，找到这些节点中到源点距离最短的节点，节点编号为 min_idx，最短路径为 min_val。
  • (2) 根据这个节点 min_idx 的最短路大小 min_val，更新 min_idx 的各个后继节点的路径长度。

上面的算法根据情况有两种实现方式，一种是用数组、另一种是用堆，下面分别看。

代码模板 (dijkstra 数组)

用数组 d 维护还没有确定最短路径的节点，每次每次都遍历一次 d 找到最小的。

时间复杂度：$O(E + V^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
vector<int> dijkstra_array(vector<vector<vector<int> > >& g, int start, int N)
{
    // dijkstra 数组实现 O(E + V^2)
    // 不能有负权

    // 存放 start 到各个点的最短路径
    vector<int> d(N + 1, -1);
    d[start] = 0;
    // 记录是否找到 start 到该点的最短路径
    vector<bool> visited(N + 1, false);
    visited[start] = true;

    // 初始化 start 到各个点的距离
    for(vector<int> son: g[start])
        d[son[0]] = son[1];

    for(int cnt = 1; cnt <= N - 1; ++cnt)
    {
        int min_val = INT_MAX / 2, min_idx = 0;
        // 遍历所有节点，找到离 start 最近的节点
        for(int i = 1; i <= N; ++i)
        {
            if(d[i] != -1 && !visited[i] && d[i] < min_val)
            {
                min_idx = i;
                min_val = d[i];
            }
        }

        // 标记离 start 最近距离节点已经找到
        visited[min_idx] = true;

        // 根据刚刚找到的距离 start 最短的节点，
        // 通过该节点更新 start 与其它节点的距离
        for(vector<int> son: g[min_idx])
        {
            if(d[son[0]] != -1) // 之前路径与当前更新路径的最小值
                d[son[0]] = min(d[son[0]], min_val + son[1]);
            else // 该节点第一次访问，直接更新
                d[son[0]] = min_val + son[1];
        }
    }
    return d;
}

代码模板 (dijkstra 堆)

另一种是使用最小堆维护还没有确定最短路径的节点，这样每轮迭代中，堆头自然就是要找的最小值。

该算法与优先级队列BFS殊途同归。

时间复杂度：$O(E\log E)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
vector<int> dijkstra_heap(vector<vector<vector<int> > >& g, int start, int N)
{
    // dijkstra 堆实现 $O(E\log E)$
    // 不能有负权

    // 存放 start 到各个点的最短路径
    vector<int> d(N + 1, INT_MAX / 2);
    d[start] = 0;

    priority_queue<vector<int>> pq; // 队列元素 (节点编号，到 start 的距离)
    pq.push({0, start});
    while(!pq.empty())
    {
        vector<int> cur = pq.top();
        pq.pop();
        int u = cur[1];
        int min_d = cur[0];
        if(d[u] < min_d) 
            continue;
        for(vector<int> son: g[u])
        {
            int v = son[0];
            int w = son[1];
            if(d[v] <= d[u] + w) 
                continue;
            d[v] = d[u] + w;
            pq.push({d[v], v});
        }
    }

    for(int& x: d)
        if(x == INT_MAX / 2)
            x = -1;
    return d;
}

算法2 : bellman ford

bellman ford 涉及到松弛操作，它的原理是著名的定理：“三角形两边之和大于第三边”

对于图中一条边 (x,y,z) 如果 d[x] <= d[y] + z，则该边 z 满足三角形不等式。

若所有边都满足三角形不等式，则各个 d[i] 就是最短路。因此算法如下：

1
2
(1) 扫描所有边(x,y,z)：若 d[y] > d[x] + z，则用 d[x] + z 更新 d[y]
(2) 重复 (A) 直至没有更新操作发生

对所有边进行 k 次松弛操作，则求出了所有点，经过的边数最多为 k 的最短路。

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
vector<int> bellman_ford(vector<vector<vector<int> > >& g, int start, int N)
{
    // bellman ford  O(VE)
    // 可以检测负环

    vector<int> d(N + 1, -1);
    d[start] = 0;

    // 进行 N - 1 轮松弛
    // 因为任意两点之间最短路最多包含 N - 1 条边
    for(int cnt = 1; cnt <= N - 1; ++cnt)
    {
        // u: 源节点，v: 子节点, w: uv 的权
        for(int u = 1; u <= N; ++u)
        {
            if(d[u] == -1) continue;
            for(vector<int> &son: g[u])
            {
                int v = son[0], w = son[1];
                // 判断能否通过 u -> v 缩短 d[v] (松弛)
                if(d[u] + w < d[v] || d[v] == -1)
                    d[v] = d[u] + w;
            }
        }
    }
    /* 可以检测负环
    for(int u = 1; u <= N; ++u)
    {
        for(vector<int> &son: g[u])
        {
            int v = son[0], w = son[1];
            if(d[u] + w < d[v])
                // 有负环
        }
    }*/
    return d;
}

算法3: spfa

SPFA 算法的基本思想是在 Bellman-Ford 算法中，很多松弛操作其实都是没有必要的，例如对于一条从 x 到 y 的边，如果连 x 都还没被松弛，那 y 肯定也还不能被 x 松弛。

用一个队列来存储已经被松弛过的点，然后用队列里的点去松弛其他点，就可以避免用一个还没有被松弛的点去松弛另外的点。

1
2
3
4
5
6
建立队列q，初始队列只含有起点 1
取队头 x
    扫描与 x 相邻的所有边 (x,y,z)
        若 d[y] > d[x] + z，则用 d[x] + z 更新 d[y]
        若 y 不在队列中，将 y 入队
    重复直至队空

如果不存在长度为负数的边，则类似于搜索中的优先级队列BFS，可以用优先级队列对 spfa 优化，每次取出当前距离源 s 最短的节点(堆顶)进行扩展。这与堆优化 dijkstra 流程完全一致，殊途同归。

如果没有负权，可以用优先级队列优化 spfa，类似于优先级队列 BFS，与 dijkstra 的堆实现殊途同归。

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<int> spfa(vector<vector<vector<int> > >& g, int start, int N)
{
    // 与 bellman ford 相同, O(VE)
    // 可以检测负环

    vector<int> d(N + 1, -1);
    d[start] = 0;
    queue<int, list<int> > q;
    q.push(start);

    // 记录每个点到 start 的节点个数
    vector<int> cnt(N + 1, 0);
    cnt[start] = 1;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(vector<int> &son: g[cur])
        {
            if(d[son[0]] == -1 || d[son[0]] > d[cur] + son[1])
            {
                cnt[son[0]] = cnt[cur] + 1;
                if(cnt[son[0]] > N) return d; // 若 son 到 start 的节点个数大于 N 了说明有负环
                // 当最短距离发生变化且不在队列中时，将该节点加入队列
                d[son[0]] = d[cur] + son[1];
                q.push(son[0]);
            }
        }
    }
    return d;
}

算法4 : floyd

floyd 中也用到了与 bellman ford 类似的松弛操作。

1
2
d[i][j] := i 到 j 的最短路径
d[i][j] = min(d[i][k] + d[k][j]) (i <= k <= j)

d 是一个矩阵，d[i][j] 为 i 到 j 的最短路径(最多经过 n - 1 条边)

作为对比，adj 邻接矩阵可以理解为 i 到 j 的经过一条边的最短路，一般地 $adj^{m}[i][j]$ 表示 i 到 j 之间恰好经过 m 条边的最短路径。

在最外层 k 在迭代过程中，迭代到 k 时，d[i][j] 表示经过编号不超过 k - 1 的节点，从 i 到 j 的最短路径，在用 Floyd 求最小环的时候用到这个事实：无向图的环。

时间复杂度 $O(V^{3})$, 但是可以把所有点之间的最短路径求出，如果求多源最短路，时间复杂度可摊销。

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> floyd(vector<vector<vector<int> > >& g, int start, int N)
{
    // floyd 需要邻接矩阵 O(V^3)
    // 可以做多源最短路
    vector<vector<int> > adj_matrix(N + 1, vector<int>(N + 1, -1));
    for(int i = 1; i <= N; ++i)
        adj_matrix[i][i] = 0;
    for(int u = 1; u <= N; ++u)
        for(vector<int> son: g[u])
            adj_matrix[u][son[0]] = son[1];

    // 遍历所有节点，其中 k 是用于松弛的点
    for(int k = 1; k <= N; ++k)
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= N; ++j)
                // 使用 k 松弛 i -> j 的最短路径
                if(adj_matrix[i][k] != -1 && adj_matrix[k][j] != -1)
                {
                    if(adj_matrix[i][j] != -1)
                        adj_matrix[i][j] = min(adj_matrix[i][j], adj_matrix[i][k] + adj_matrix[k][j]);
                    else
                        adj_matrix[i][j] = adj_matrix[i][k] + adj_matrix[k][j];
                }

    vector<int> d(N + 1, -1);
    for(int i = 1; i <= N; ++i)
        d[i] = adj_matrix[start][i];

    return d;
}

代码 (C++)

当有了 shortest_path 之后，本题的代码如下。五种算法分别对于以下代码中的 dijkstra_array、dijkstra_heap、bellman_ford、spfa、floyd。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        vector<vector<vector<int> > > g(N + 1);
        for(vector<int> &edge: times)
            g[edge[0]].push_back({edge[1], edge[2]});

        // 求带权邻接表的最短路
        vector<int> d = dijkstra_array(g, K, N);
        // vector<int> d = dijkstra_heap(g, K, N);
        // vector<int> d = bellman_ford(g, K, N);
        // vector<int> d = spfa(g, K, N);
        // vector<int> d = floyd(g, K, N);

        int res = 0;
        for(int i = 1; i <= N; i++)
        {
            if(d[i] == -1)
                return -1;
            res = max(res, d[i]);
        }
        return res;
    }
};
Share