力扣2642-设计可以求最短路径的图类

摘要: 加边松弛操作

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

---

在文章 Floyd算法 中我们了解到了求最短路径的 Floyd 算法。理解这个算法需要一些动态规划的概念，其中阶段的定义与推导比较特殊，涉及到松弛操作的概念，也就是每推导一个阶段就相当于进行了一次松弛操作。

当我们推完了所有的阶段，dp 数组中就有了所有点对之间的最短路径。因此当需要多次查询不同点对之间的最短路径时，用 Floyd 算法是比较合适的，先$O(N^{3})$地预处理出 dp 数组，然后就可以 $O(1)$ 地响应最短路径的查询了。

本文的题目更进了一步，图中可能有加边的操作，每次加边，原来的 dp 数组就需要一轮更新了，这种更新可以视为一种由加边引入的松弛操作。

题目

• 2642. 设计可以求最短路径的图类

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。

请你实现一个 Graph 类：

• Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
• addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost] 。数据保证添加这条边之前对应的两个节点之间没有有向边。
• int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径 最小 代价。如果路径不存在，返回 -1 。一条路径的代价是路径中所有边代价之和。

提示：

1 <= n <= 100
0 <= edges.length <= n * (n - 1)
edges[i].length == edge.length == 3
0 <= fromi, toi, from, to, node1, node2 <= n - 1
1 <= edgeCosti, edgeCost <= 1e6
图中任何时候都不会有重边和自环。
调用 addEdge 至多 100 次。
调用 shortestPath 至多 100 次。

示例 1：

输入：
[“Graph”, “shortestPath”, “shortestPath”, “addEdge”, “shortestPath”]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
输出：
[null, 6, -1, null, 6]
解释：
Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
g.shortestPath(3, 2); // 返回 6 。从 3 到 2 的最短路径如第一幅图所示：3 -> 0 -> 1 -> 2 ，总代价为 3 + 2 + 1 = 6 。
g.shortestPath(0, 3); // 返回 -1 。没有从 0 到 3 的路径。
g.addEdge([1, 3, 4]); // 添加一条节点 1 到节点 3 的边，得到第二幅图。
g.shortestPath(0, 3); // 返回 6 。从 0 到 3 的最短路径为 0 -> 1 -> 3 ，总代价为 2 + 4 = 6 。

题解

算法：Floyd算法+加边松弛

Floyd 算法回顾

首先将 Floyd 算法解决多源最短轮径的算法做个回顾。

记 d[i][j] 表示从 i 到 j 的最短路径。初始值为 INT_MAX / 2，表示 i, j 之间尚未发现路径。随着一轮一轮的迭代，d[i][j] 的值会进行更新（每一轮迭代相当于动态规划的阶段往前推导一次）。迭代完成后，d[i][j] 的值就是 i 到 j 的最短路径了，如果 d[i][j] 仍然为 INT_MAX / 2，则表示从 i 到 j 没有路径。

下面我看一下如何求出 d[i][j]，这也是 Floyd 算法解决的问题。该算法整体是一个动态规划算法，DP 推导过程就是从小的子图到大的子图最后到全图的过程。算法如下：

状态定义：
dp[k][i][j] := 在包含 0 ~ k 这 k 个点的子图上，点对 i, j 之间的最短路径。

初始化：
dp[0][i][j] = INT_MAX / 2
dp[0][i][i] = 0
dp[0][edge[0]][edge[1]] = edge[2]

状态转移：
dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

从动态规划的角度看，k 是 DP 问题的阶段，i, j 是附加状态，因此实现时 k 的循环需要放在 i, j 的循环的外面。

转移方程中 dp[k-1][i][j] 是在节点为 0,1,...,k-1 的子图中 i 到 j 的最短距离。此时考虑 k 点，在此前阶段中 i, j 之间的最短路径是不含 k 点的，在当前阶段把 k 点也引入，相当于 i, j 之间的最短路径可以使用的点的范围扩大了，因此推导阶段 k 的过程也称为松弛操作。

在当前阶段，最短路径的可选点集中增加了 k 点，dp[k-1][i][k] + dp[k-1][k][j] 是经过 k 点的新路径的长度，该路径从 i 出发，先以最短路径到 k （不在 0,1,...,k-1 的子图中，在前一阶段已经求出），然后从 k 再到 j 的过程类似。在扩展新点 k，也就是推导当前阶段时，可以复用此前阶段 0~k-1 的结果，这是动态规划的思想。

由于 dp[k][i][j] 只和 dp[k-1][...][...] 有关，通过滚动数组可以省略掉 k 这一维。

加边松弛

在上述 Floyd 算法中，当所有阶段推导完后，dp[i][j] 即为当前图中从 i 到 j 的最短路径。

这里的难点是图中会有加边的情况，每加一条边，dp[i][j] 都有可能发生变化，也就是可能取到更小的值，因此需要对 dp 进行更新。

假设增加了边 (u, v, w)，在之前推导完的 dp 中代表的各个点对之间的最短路径是不含边 uv 的，现在把边 uv 引入，i, j 之间的最短路径的考虑范围更大了，就可能取到更小的值。

以上过程与前面的 Floyd 算法中推导阶段时的思路类似。因此增加边 (u, v, w) 后，dp 的一轮更新可以也可以视为松弛操作，前面的 Floyd 算法中推导阶段的过程是由加点引入的松弛，这里是由加边引入的松弛。

dp 的具体更新过程就是考虑每个点对 i, j，由于边 uv 的引入，从 i 到 j 的最短路就有了先走 i 到 u 的最短路，然后走 uv 这条边，然后再走 v 到 j 最短路，最终形成了一条路径，这条路径如果比此前的 dp[i][j] 更短，就把它更新进去：

dp[i][j] = min(dp[i][j], dp[i][u] + w + dp[v][j])

代码 (Python)

预处理阶段完成 Floyd 算法的推导需要 $O(N^{3})$ 的时间复杂度。

每更新一条边，需要 $O(N^{2})$ 的时间复杂度来对 dp 做一轮松弛更新。

class Graph:
    def __init__(self, n: int, edges: List[List[int]]):
        self.INF = int(1e11)
        self.n = n
        self.dp = [[self.INF for _ in range(n)] for _ in range(n)]
        for i in range(n):
            self.dp[i][i] = 0
        for u, v, w in edges:
            self.dp[u][v] = w

        for k in range(n):
            for i in range(n):
                for j in range(n):
                    self.dp[i][j] = min(self.dp[i][j], self.dp[i][k] + self.dp[k][j])

    def addEdge(self, edge: List[int]) -> None:
        u, v, w = edge
        for i in range(self.n):
            for j in range(self.n):
                self.dp[i][j] = min(self.dp[i][j], self.dp[i][u] + w + self.dp[v][j])


    def shortestPath(self, node1: int, node2: int) -> int:
        ans = self.dp[node1][node2]
        return ans if ans != self.INF else -1

---