查找图表上每对节点的所有最短路径

Question

我有大约70k节点和250k边缘,图形不一定连接.显然,使用有效的算法至关重要.您有什么推荐的吗？

作为旁注,我很欣赏如何在多台机器之间划分任务的建议 - 这种问题甚至可能吗？

谢谢

Answer 1

您可以使用Floyd-Warshall 算法。它正好解决了这个问题。

复杂度为O(V^3)。

还有Johnson算法，复杂度为O(V^2*log V + VE)。后者也很容易分发，因为它运行 Dijkstra 算法 V 次，可以并行完成。