我有大约 70,000 个节点和 250,000 个边，并且该图不一定是连通的。显然，使用高效的算法至关重要。你有什么建议？
作为旁注，我将不胜感激关于如何在多台机器之间分配任务的建议——这种问题是否可能？
谢谢
最佳答案
您可以使用 Floyd-Warshall algorithm .它正好解决了这个问题。
复杂度为 O(V^3)。
还有Johnson's algorithm复杂度为 O(V^2*log V + VE)。后者也易于分发，因为它运行 Dijkstra 算法 V 次，可以并行完成。
关于algorithm - 从图中的每对节点查找所有最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2421605/