graph - 图中所有对的最短路径均指向非负加权边

Question

我有一个带有非负加权边的有向图，其中两个顶点之间有多个边。

我需要计算所有对的最短路径。该图非常大（2000 万个顶点和 1 亿条边）。Floyd-Warshall 是最好的算法吗？有没有很好的库或工具来完成这个任务？

Answer 1

对于具有非负循环的有向图，存在几种全对全最短路径算法，Floyd-Warshall 可能是最著名的，但是根据您提供的数字，我认为您无论如何都会遇到内存问题（时间可能是一个问题，但您可以找到可以轻松且大规模并行化的全对全算法）。
与您使用的算法无关，您必须将结果存储在某处。存储 20,000,000² = 400,000,000,000,000 条路径长度（如果不是完整路径本身）至少会使用数百 TB。
访问这些结果中的任何一个都可能比计算最短路径（内存墙）更长，这可以在不到一毫秒的时间内完成（取决于图形结构，您可以找到比 Dijkstra 或任何优先级快得多的技术基于队列的算法）。

老实说，我认为您应该寻找一种不需要计算所有最短路径的替代方法。或者，为了应用不同的算法，研究你的图的结构（DAG，结构良好的图，易于分区/聚类，几何/地理信息......），因为在一般情况下，我看不到任何方法。

例如，对于您提供的数字，考虑到它的尺寸，平均大约 5 的度数构成了一个相当稀疏的图。然后，图分区方法可能非常有用。