时间戳

首页 > 解决方案 > 为什么 Floyd Warshall 算法只需要 O(n^2) 空间？

algorithm - 为什么 Floyd Warshall 算法只需要 O(n^2) 空间？

问题描述

我正在研究 Floyd Warshall 算法并且有一个问题。为什么这个算法只需要 O(v^2) 空间？

天真地，我知道它在 O(v^3) 中工作得很好，但是当我看到 O(v^2) 的伪代码时，我很好奇它是如何工作的。 

D ← W;
   for k ← 1 to n do
      for i ← 1 to n do
          for j ← 1 to n do
            dij ← min(d_ij, d_ik + d_kj);
return D;

在这里，我们比较了 d_ij 和 d_ik + d_kj，但是由于没有上标，在 (for i) 和 (for j) 迭代期间，d_ik 或 d_kj 可能已经更新为第 k 个上标。Floyd Warshal 总是比较第 k-1 个超级脚本的加法，但这种算法有时不会。这怎么可能是真的？

标签： algorithmshortest-pathfloyd-warshall

解决方案

推荐阅读