Floyd Warshall使用邻接表 [英] Floyd Warshall using adjacency lists

问题描述

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

Is is possible to code Floyd Warshall using adjacency lists? I have to process a million vertices from a text file and hence, adjacency matrices is not a solution. Any implementation already available? Please help.

推荐答案

Floyd Warshall使用邻接表实现，但它会在盯着算法之前在内部将邻接表转换为矩阵.如果您的图形不是稀疏的，那么使用adj列表而不是矩阵将无济于事，因为无论如何您都需要扫描所有边缘.但是，如果您的图非常稀疏，则可能需要考虑从每个节点运行Dijkstra'a最短路径算法，而不是使用Floyd Warshall.如Anh Huynh在其他答复中提到的，如果您确实知道| E |， 〜| V | log ^ k | V |在0< = k的情况下，为每个节点运行Dijkstra的算法将比Floyd Warshall拥有更好的时间复杂性.

Floyd Warshall Implementation using adjacency list but it internally converts the adjacency list to matrix before staring the algo. If your graph is not sparse then using adj list instead of matrix won't help because anyways you need to scan all edges. But if your graph is very sparse then you might want to consider running Dijkstra'a shortest path algo from each node instead of using Floyd Warshall. As mentioned by Anh Huynh in the other response if you definitely know that |E| ~ |V| log^k |V| where 0 <= k then running Dijkstra's algo for each node will give you better time complexity than Floyd Warshall.

这篇关于Floyd Warshall使用邻接表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！