java - Floyd Warshall 使用邻接表

Question

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

Answer 1

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

示例:

首先，您的图形有 2 条边(1-2、2-3)。所以你初始化邻接矩阵:

调整[1][2] = 1; (表示在 1 和 2 之间有边)

调整[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。