Floyd–Warshall 算法：编码面试指南

长话短说: Floyd-Warshall 算法通过动态规划计算所有对的最短路径。从图中初始化一个距离矩阵，然后对于每个中间顶点 k 用 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 更新每对。它在 O(V³) 时间和 O(V²) 空间中运行，并且可以通过负对角线条目暴露负循环。

什么是弗洛伊德-沃歇尔算法？

Floyd-Warshall 是一种动态规划算法，用于计算每个有序顶点对之间的最短路径。它适用于有向或无向加权图，并允许负边。然而，如果存在相关的负权环，则某些最短路径没有有限的最小值，因为重复遍历该环会不断减少路径成本。

该算法令人难忘，因为它将全局路径问题转化为一个决策：对于当前中间顶点 k，从 i 到 j 的已知路径是否更好，还是从 i 到 k，然后从 k 到 j？

怎样推导出重复性呢？

定义 D(k, i, j) 为从 i 到 j 的最短距离，其中间顶点只能来自前 k 个顶点。最短允许路径要么避开顶点 k，保留 D(k−1, i, j)，要么使用 k 并分成从 i 到 k 的最佳允许路径加上从 k 到 j 的最佳允许路径。

这给出了递归式：

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

由于阶段 k 仅以兼容的方式依赖于阶段 k−1 值，因此可以就地更新矩阵。这个推理也解释了关键的循环顺序：k 必须是最外层的循环。将 i 或 j 放在外面会更改不变量，并且可能会错误地使用部分允许的路径。

如何初始化距离矩阵？

创建一个 V × V 矩阵。将 dist[i][i] 设置为零，将直接边的单元设置为其权重，并在不存在直接边时使用无穷大。如果平行边可能，请保持最小的直接权重。在添加两个距离之前，请验证两者都是有限的，以便无穷大的哨兵不会溢出或创建错误的候选者。

你如何在采访中追踪弗洛伊德-沃歇尔？

将矩阵行标记为源，将列标记为目标。显示初始矩阵，然后选择一个 k 并评估代表性单元。对于每个单元格，将当前值与经过 k 的路线进行比较。仅当两个段均可到达并且新的总和较小时才更新。

通常不需要为大型示例绘制每个矩阵。追踪足够的单元格来证明不变性，包括一项改进和一项不变的值。说明完成 k 后，每个矩阵条目在其中间顶点仅限于处理集的路径中都是最优的。

你应该写什么伪代码？

使用三个嵌套循环，k 在外面：

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

解释有限检查和数字类型。在具有大整数哨兵的语言中，将无穷大添加到负值可能看起来有限或溢出。防护是正确性的一部分，而不仅仅是实现细节。

时间和空间复杂度是多少？

这三个循环检查 k、i 和 j 的每种组合，因此运行时间为 O(V³)。距离矩阵占据 O(V²) 空间。就地更新避免了三维表，而用于路径重建的下一跳或前驱矩阵增加了 O(V²) 更多空间。

Floyd-Warshall 通常对适度密集的图很有吸引力，因为它的实现紧凑且可预测。对于具有非负边的大型稀疏图，从每个源运行 Dijkstra 可能会更有效。在选择之前始终比较所需的输出、图形密度、权重约束和顶点数。

如何重建实际的最短路径？

距离本身并不能揭示顶点序列。当存在从 i 到 j 的直接边时，维护一个初始化为 j 的 next[i][j] 矩阵。每当通过 k 的路由改善 dist[i][j] 时，请将 next[i][j] 设置为 next[i][k]。要重建路径，请重复从当前顶点移动到 next[current][destination] 直到到达目的地。

在重建之前检查不可达对，并防止出现负循环情况。如果一对可以走负循环然后到达目的地，则没有有限的最短路径可以重建。

Floyd-Warshall 如何检测负循环？

算法完成后，检查对角线。值 dist[v][v] < 0 证明负权循环可以从 v 到达并且可以返回到 v。这比仅仅找到负边更强；负边可以存在于具有完全有效的最短路径的图中。

如果面试官询问哪些对受到影响，请确定每个 i 和 j，其中 i 可以到达顶点 v，v 可以到达 j。这些对可以在负循环中循环任意多次，因此它们的最短路径值不是有限的。

什么时候应该选择另一种最短路径算法？

对未加权图使用广度优先搜索，对具有非负权重的单源问题使用 Dijkstra 搜索，当负权重或可达到的负循环检测很重要时，对单源问题使用 Bellman-Ford 搜索。当需要所有对距离并且可接受立方时间时，Floyd-Warshall 是直接选择。

你应该避免哪些面试错误？

不要将 k 放入另一个循环中，忘记对角线上的零，在没有保护的情况下添加无穷大，将负边与负循环混淆，或者声称 O(V²) 矩阵空间在每个表示中自动包含输入。澄清该图是否有向，是否存在平行边，以及采访者是否需要距离、路径或受循环影响的对。

练习编码面试助理工作流程，比较贝尔曼-福特算法，并查看大O复杂性备忘单。

常见问题

练习不变量，而不仅仅是循环

YesToTheOffer 可以帮助构建编码解释，将其纳入您的私人准备笔记中，检查边缘情况，并保存面试记录以供以后查看。