graph-theory - 关于 Floyd-Warshall 算法的 O(n^2) 存储

Question

为什么 Floyd-Warshall 算法中有存储？如果使用链表而不是 N × N 矩阵，会不会比这更少？

Answer 1

该链表的最坏情况大小仍然是O(n^2)（我认为？我不完全确定我理解您建议如何使用它），但查找成本将足够昂贵以改变整个算法的渐近复杂度（链表上的操作与已知大小的矩阵上的操作具有不同的复杂性）。