是否可以使用邻接表对 Floyd Warshall 进行编码？我必须处理文本文件中的一百万个顶点，因此邻接矩阵不是解决方案。已有可用的实施吗？请帮忙。
您不能将 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] = 2 （意味着有1 和 3 之间的边）；
我不知道图中有多少条边以及要解决的时间限制，但如果您需要计算图中所有对之间的最短路径，您可以执行 |V|优先级队列的 Dijkstra 时间复杂度为 |V| * max( |V|log|V| , |E| ) 优于 Floyd Warshall 的 |V|^3。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
