DSA Interview Prep · 课时

Floyd-Warshall：所有点对最短路径

Q: 「Floyd-Warshall：所有点对最短路径」课时是免费的吗？

是的 — 「Floyd-Warshall：所有点对最短路径」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。

Q: 「Floyd-Warshall：所有点对最短路径」这节课中我会学到什么？

使用三重循环的 Floyd-Warshall 算法填充所有点对距离矩阵，并应用它找出任意节点对之间所需的最少跳数。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 DSA Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

Q: 「Floyd-Warshall：所有点对最短路径」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 DSA Interview Prep 课中编写并运行代码吗？

能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

使用三重循环的 Floyd-Warshall 算法填充所有点对距离矩阵，并应用它找出任意节点对之间所需的最少跳数。

Floyd-Warshall：所有点对最短路径 是 CoddyKit 上的免费 DSA Interview Prep 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。

全源最短路径

弗洛伊德-沃舍尔算法计算带权图中每一对节点之间的最短路径，包括含有负权边但不含负环的图。从每个源点运行一次戴克斯特拉算法需要 O(V × (V+E) log V) 的时间；无论边的密度如何，弗洛伊德-沃舍尔算法的复杂度都是 O(V³)。对于 V ≤ 500 的稠密图，弗洛伊德-沃舍尔算法通常更简单，速度也相当。

核心思想：中间节点

弗洛伊德-沃舍尔算法的洞见是：dp[i][j][k] 表示从 i 到 j、且只使用节点 {0, 1, ..., k} 作为中间节点的最短路径。最短路径要么经过节点 k 作为中间节点，要么不经过。如果经过：dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]。如果不经过：dp[i][j][k] = dp[i][j][k-1]。由于第三个维度只会向前推进，因此可以将其消除，直接进行原地更新。

距离矩阵的初始化

首先创建一个 V×V 矩阵：对于自身距离，设置 dist[i][i] = 0；对于直接相连的边，设置 dist[i][j] = weight；对于不相连的节点，设置 dist[i][j] = inf。然后遍历所有中间节点 k，更新节点对 (i, j)。必须先执行以 k 为外层的循环，这样才能正确地逐步构建经过越来越多允许的中间节点的路径。

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w  # directed graph
    
    for k in range(V):       # intermediate node
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

带示例的完整实现

下面跟踪一个 4 节点图上的弗洛伊德-沃舍尔算法。每处理完一个中间节点 k，矩阵就会补充经过节点 k 的更短路径。该算法通过逐步构建最短路径，自然地处理多次跳转。

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
    print([x if x != float('inf') else 'INF' for x in row])

检测负环

运行弗洛伊德-沃舍尔算法后，请检查主对角线：如果存在任何 dist[i][i] < 0，则表示有一个经过节点 i 的负环。这是因为负环允许以负成本从 i 回到 i。如果不存在负环，所有对角线元素都会保持为 0。

def has_negative_cycle_fw(V, edges):
    dist = floyd_warshall(V, edges)
    for i in range(V):
        if dist[i][i] < 0:
            return True  # negative cycle through node i
    return False

# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg))  # True

路径重建

要重建从 i 到 j 的实际路径，请维护一个 next[i][j] 矩阵：对于直接相连的边，初始设置 next[i][j] = j。通过中间节点 k 更新时，设置 next[i][j] = next[i][k]。恢复路径时，从 i 开始，沿着 next 指针追踪，直到到达 j。这会增加 O(V²) 的空间开销，并使每次路径重建需要 O(V) 的时间。

def fw_with_path(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    nxt = [[None]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w; nxt[u][v] = v
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def get_path(nxt, i, j):
    if nxt[i][j] is None: return []
    path = [i]
    while i != j:
        i = nxt[i][j]; path.append(i)
    return path

传递闭包

一个更简单的变体是：传递闭包回答所有节点对中的“节点 j 是否可以从节点 i 到达？”将距离替换为布尔值：reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])。这相当于使用布尔 OR 代替加法和取最小值的弗洛伊德-沃舍尔算法。请将 reach[i][i] = True 初始化，并将直接相连的边对应的 reach[i][j] = True。

def transitive_closure(V, edges):
    reach = [[False]*V for _ in range(V)]
    for i in range(V):
        reach[i][i] = True
    for u, v, _ in edges:
        reach[u][v] = True
    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2])  # True (0 can reach 2 via 0->1->2)

复杂度与适用场景

弗洛伊德-沃舍尔算法：时间复杂度为 O(V³)，空间复杂度为 O(V²)。对于 V ≤ 300 的稠密图（E ≈ V²），它比运行 V 次戴克斯特拉算法更快（在这种情况下，后者的复杂度同样为 O(V³)）。对于 V = 1000、E = 3000 的稀疏图，运行 V 次戴克斯特拉算法的成本为 O(V×E×log V) ≈ 33M，而弗洛伊德-沃舍尔算法的成本为 O(V³) = 10⁹，此时应选择戴克斯特拉算法。请掌握每种算法的适用场景。

所有点对之间的最少跳数

将所有边的权重设为 1（或者使用布尔邻接矩阵，通过加法而非取最小值来执行弗洛伊德-沃舍尔算法）：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。这样可以计算所有点对之间的最少跳数——结果等同于对所有点对执行 BFS，但只需进行一次 O(V³) 的弗洛伊德-沃舍尔遍历即可。

def min_hops_all_pairs(V, adj_list):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
        for j in adj_list[i]:
            dist[i][j] = 1
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0])  # [0, 1, 1, 2, INF]

面试场景：面试官询问弗洛伊德-沃舍尔算法时

在以下问题中，面试官可能会考查弗洛伊德-沃舍尔算法：（1）求小型图中所有点对之间的距离；（2）判断是否存在总权重为负的环；（3）在约束传播问题中计算最短路径；（4）题目明确要求 O(V³) 解法且 V ≤ 200。请始终提到三层循环结构，以及为了保证正确性而不能存在负环这一要求。

使用弗洛伊德-沃舍尔算法处理无向图

对于无向图，请为每条边添加两个方向：dist[u][v] = dist[v][u] = weight。算法的其余部分完全相同。得到的矩阵是对称的：对于所有点对，均有 dist[i][j] == dist[j][i]。初始化时请注意不要误将边设置为单向边——无向边必须在执行三层循环之前，沿两个方向添加到初始矩阵中。

def fw_undirected(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # both directions for undirected
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

快速检查

请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。

课程回顾

在本课中，您学到了：弗洛伊德-沃舍尔算法通过三层嵌套循环和递推式 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 计算所有点对之间的最短路径；算法完成后，通过检查是否存在 dist[i][i] < 0 可以检测负环；以及该算法的时间复杂度为 O(V³)，空间复杂度为 O(V²)。接下来，我们将通过网络延迟时间问题和路径重建技术，继续学习最短路径的应用。

常见问题解答