java - Floyd Warshall 使用邻接表

Question

是否可以使用邻接列表对 Floyd Warshall 进行编码？我必须处理来自文本文件的一百万个顶点，因此，邻接矩阵不是解决方案。任何实现已经可用？请帮忙。

Answer 1

您不能将 Floyd Warshall 与邻接列表一起使用，因为当它起作用时，它会产生新的边缘。

例子 ：

首先，您的图表有 2 条边（1-2、2-3）。所以你初始化邻接矩阵：

adj[1][2] = 1; （表示边缘在 1 和 2 之间）

adj[2][3] = 1; （意味着边缘在 3 和 2 之间）

adj[1][3] = +oo; （表示 1 和 3 之间没有边）

当 FW 工作时，将添加边 1-3，因为 adj[1][2] + adj[2][3] < adj[1][3] => adj[1][3] = 2 （意味着有1 和 3 之间的边）；

我不知道你的图中有多少条边和解决时间限制，但如果你需要计算图中所有对之间的最短路径，你可以做 |V| 具有复杂度的优先级队列的 Dijkstra 时间为 |V| * max( |V|log|V| , |E| ) 优于 Floyd Warshall 的 |V|^3。

Answer 2

Floyd Warshall 使用邻接列表实现，但它在启动算法之前在内部将邻接列表转换为矩阵。如果您的图形不是稀疏的，那么使用 adj 列表而不是矩阵将无济于事，因为无论如何您都需要扫描所有边。但是，如果您的图表非常稀疏，那么您可能需要考虑从每个节点运行 Dijkstra'a 最短路径算法，而不是使用 Floyd Warshall。正如 Anh Huynh 在另一个回复中所提到的，如果您确实知道 |E| ~ |V| 对数^k |V| 其中 0 <= k 然后为每个节点运行 Dijkstra 的算法将为您提供比 Floyd Warshall 更好的时间复杂度。