Почему алгоритму Флойда Варшалла нужно только пространство O (n ^ 2)?

Question

Я изучаю алгоритм Флойда Варшалла и у меня есть предложение. Почему этот алгоритм требует только 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, но поскольку суперскрипта нет, есть вероятность, что d_ik или d_kj уже были обновлены до k-го суперскрипта во время (для i) и (для j) итерации. Флойд Варшал всегда сравнивает добавление k-1-го суперскрипта, но этот алгоритм иногда не делает. Как это может быть правдой?