Floyd Warshall Algorithm

Q: Floyd Warshall 算法能处理负权边吗？

是的，只要不存在负环，也就是权重总和小于 0 的循环。如果存在负环，最短路径就没有定义，表格也会显示这一点：一些 dist[i][i] 最终小于 0。

中等最短路径动态规划

+10

给定一个有向图，它有 n 个节点，编号从 0 到 n-1，并用一个 n 行 n 列的矩阵表示：matrix[i][j] 表示从节点 i 到节点 j 的边的权重；如果没有边，则为 -1；并且 matrix[i][i] 为 0。路径的长度是其所有边权重之和。

返回一个 n 行 n 列的矩阵，其中 [i][j] 表示从节点 i 到节点 j 的最短路径长度；如果从节点 i 无法到达节点 j，则为 -1。

函数

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: 边的权重：matrix[i][j] 表示从 i 到 j 的边的权重，如果不存在该边，则为 -1
返回值integer-2d-array: 每对节点之间的最短距离，没有路径时为 -1

约束条件

1 ≤ n ≤ 100，其中 n = matrix.length = matrix[i].length
matrix[i][i] = 0
当 i ≠ j 时，matrix[i][j] 是 -1（没有边），或者满足 0 ≤ matrix[i][j] ≤ 1000。
边是单向的：matrix[i][j] 和 matrix[j][i] 互不影响。

示例

输入: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
输出: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
解释: 通过节点 1，节点 0 到达节点 2 的距离为 6，而不是 11；到达节点 3 的距离为 9。节点 1 通过节点 2 到达节点 0 的距离为 3。没有边从节点 3 出发，因此其行在对角线之外的值为 -1。

输入: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
输出: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
解释: 从 2 到 1 的边权重为 0，所以 0 → 2 → 1 的代价为 1，小于直接前往的 6。没有边从节点 1 出发，也没有边进入节点 0，因此这些节点对仍为 -1。

进阶

构建表格后，有一条边的成本降低了。你能否在 O(n²) 时间内更新所有距离，而不是再次运行 O(n³) 次循环？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

你需要求出每对节点之间的最短路径。Floyd-Warshall 用一个三重循环就能找到全部 n² 个答案。每一轮都会让路径多经过一个节点，每对节点只需比较一次：目前找到的最佳路径和经过新节点的路径。

将每条路径延伸一条边，直到不再发生变化

结果正确，但无法在最大的测试中运行完毕

思路

从矩阵开始，每一轮都为每条路径延长一条边：从 i 到 m 的路径加上边 m → j，就得到一条从 i 到 j 的路径；如果这条路径更短，就保留它。重复执行，直到某一轮不再有任何变化。

经过 p 轮后，就能找到最多有 p+1 条边的所有最短路径。没有负权重，因此某条最短路径不会包含循环，且最多有 n-1 条边。循环执行若干轮后，每个距离都会确定。对于 100 个节点，一轮需要 n³ = 10^6 步；较长的最短路径链最多需要 n 轮：O(n⁴)，最多需要 10^8 步。

算法

将 matrix 复制到 dist。
对于每个 i、m 和 j：如果 dist[i][m] 和 matrix[m][j] 都存在，就计算它们的和。
如果 dist[i][j] 是 -1，或大于这个和，就存储这个和，并记下本轮发生了变化。
重复执行这一轮，直到没有任何变化，然后返回 dist。

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall：每轮多允许一个中间点

思路

限制一条路线在起点和终点之间可以经过哪些节点。表格最初是邻接矩阵，也就是没有中间停靠点的路线。经过第 k 轮后，dist[i][j] 表示所有中间停靠点都位于节点 0 到 k 之间的最短路线，最后一轮得出的就是答案。

在第 k 轮中，允许经过 k 的最优路线要么跳过 k，而表格中已经记录了这条路线；要么经过 k 一次，因为没有负权重。路线的两段只经过节点 0 到 k-1，所以它们分别是 dist[i][k] 和 dist[k][j]。

在第一个示例中，第 1 轮将节点 0 到节点 2 的直接路线长度 11 替换为 6。第 2 轮得出节点 0 到节点 3 的路线长度为 6 + 3 = 9，其中长度为 6 的路线中包含经过节点 1 的停靠点。

只需要一张表：第 k 行和第 k 列在第 k 轮中不会改变，因为 dist[k][k] 为 0。

算法

将 matrix 复制到 dist 中；-1 表示尚未找到路线。
对于从 0 到 n-1 的 k，以及每个 i 和 j：如果 dist[i][k] 或 dist[k][j] 是 -1，就跳过这一对。
否则，计算 via = dist[i][k] + dist[k][j]。
如果 dist[i][j] 是 -1，或大于 via，就将其设为 via。
返回 dist。

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

易错点和边界情况

把 -1 当作权重加入：-1 + 5 = 4 看起来像一条路线。先检查两个部分，并将 dist[i][j] 中的 -1 视为比任何路线都差。
把对 k 的循环放在内层。经过站点 0 到 k-1 的路线必须先确定下来，然后才能引入节点 k。
把最大 int 当作无穷大：将两个值相加会导致 32 位 int 溢出，得到负距离。实际距离最多为 99 × 1000 = 99,000，因此 10^9 是安全的，因为 2 × 10^9 小于 2^31-1。
假设边是双向的。在第二个示例中，节点 0 可以到达节点 1，但节点 1 无法到达任何节点。
运行广度优先搜索，它会忽略权重：在第一个示例中，它报告从节点 0 到节点 2 的距离是 11，而不是 6。

常见问题3

Floyd Warshall 算法的时间复杂度是多少？

对于 n 个节点，时间复杂度为 O(n³)：对节点进行三层嵌套循环，每步执行一次加法和一次比较，100 个节点需要 10^6 步。距离表的空间复杂度为 O(n²)，可以原地更新。

Floyd Warshall 算法能处理负权边吗？

是的，只要不存在负环，也就是权重总和小于 0 的循环。如果存在负环，最短路径就没有定义，表格也会显示这一点：一些 dist[i][i] 最终小于 0。

什么时候应该使用 Floyd Warshall 算法，而不是 Dijkstra 算法？

对于最多有几百个节点的稠密图，使用 Floyd-Warshall 算法计算每对节点之间的路径。使用数组从每个节点运行 Dijkstra，时间复杂度为 O(n³)；使用堆则为 O(n · E log n)，在大型稀疏图上更有优势。Floyd-Warshall 不需要堆，并且支持负权边，而 Dijkstra 不支持。

def shortestDistances(matrix):
    # 在这里编写代码

测试 #1

测试 #2

参数

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

预期输出

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]