我有一个非负加权边的有向图，其中两个顶点之间有多个边。
我需要计算所有对最短路径。该图非常大（20 milion顶点和100 mil边缘）。 Floyd-Warshall是最好的算法吗？有一个很好的库或工具来完成这项任务？
对于具有非负周期的有向图，存在几种全对齐的最短路径算法，Floyd-Warshall可能是最着名的，但是根据你给出的数字，我认为你在任何情况下都会有内存问题（时间可能是一个问题，但你可以找到所有可以轻松和大规模并行化的算法。 独立于您使用的算法，您必须将结果存储在某处。并且存储20,000,000²= 400,000,000,000,000个路径长度（如果不是完整路径本身）将至少使用数百TB。 访问任何这些结果可能比计算一条最短路径（内存墙）更长，这可以在不到一毫秒的时间内完成（取决于图形结构，您可以找到比Dijkstra或任何优先级快得多的技术）基于队列的算法）。
我认为你应该寻找一种替代方案，在这种方法中，不需要计算所有最短的路径，这是最好的。或者，研究图形的结构（DAG，结构良好的图形易于分区/聚类，几何/地理信息......）以便应用不同的算法，因为在一般情况下，我没有看到任何方法。
例如，根据您给出的数字，考虑到其尺寸，平均度数约为5会产生相当稀疏的图形。图形分区方法可能非常有用。