图中所有对的最短路径均以非负加权边为导向
All pairs shortest paths in graph directed with non-negative weighted edges
我有一个带非负加权边的有向图，其中两个顶点之间有多个边。
我需要计算所有对的最短路径。
这个图非常大（2000 万个顶点和 1 亿个边）。
Floyd–Warshall 是最好的算法吗？有没有好的库或工具来完成这个任务？
对于具有非负循环的有向图，存在几种全对全最短路径算法，Floyd-Warshall 可能是最著名的算法，但是根据您提供的数字，我想您无论如何都会有记忆问题（时间可能是个问题，但您可以找到可以轻松大规模并行化的 all-to-all 算法）。
独立于您使用的算法，您必须将结果存储在某个地方。并且存储 20,000,000² = 400,000,000,000,000 路径长度（如果不是完整路径本身）将至少使用数百 TB。
访问这些结果中的任何一个可能比计算一条最短路径（内存墙）要长，后者可以在不到一毫秒内完成（根据图形结构，您可以找到比 Dijkstra 或任何优先级快得多的技术基于队列的算法）。
老实说，我认为您应该寻找一种不需要计算所有到所有最短路径的替代方法。或者，研究你的图的结构（DAG，结构良好的图容易partition/cluster，geometric/geographic信息...）以便应用不同的算法，因为在一般情况下，我看不到任何方式。
例如，对于您提供的数字，考虑到它的维度，平均度数约为 5 可以构成一个相当稀疏的图。图分区方法可能会非常有用。
我有一个带非负加权边的有向图，其中两个顶点之间有多个边。
我需要计算所有对的最短路径。 这个图非常大（2000 万个顶点和 1 亿个边）。 Floyd–Warshall 是最好的算法吗？有没有好的库或工具来完成这个任务？
对于具有非负循环的有向图，存在几种全对全最短路径算法，Floyd-Warshall 可能是最著名的算法，但是根据您提供的数字，我想您无论如何都会有记忆问题（时间可能是个问题，但您可以找到可以轻松大规模并行化的 all-to-all 算法）。
独立于您使用的算法，您必须将结果存储在某个地方。并且存储 20,000,000² = 400,000,000,000,000 路径长度（如果不是完整路径本身）将至少使用数百 TB。
访问这些结果中的任何一个可能比计算一条最短路径（内存墙）要长，后者可以在不到一毫秒内完成（根据图形结构，您可以找到比 Dijkstra 或任何优先级快得多的技术基于队列的算法）。
老实说，我认为您应该寻找一种不需要计算所有到所有最短路径的替代方法。或者，研究你的图的结构（DAG，结构良好的图容易partition/cluster，geometric/geographic信息...）以便应用不同的算法，因为在一般情况下，我看不到任何方式。
例如，对于您提供的数字，考虑到它的维度，平均度数约为 5 可以构成一个相当稀疏的图。图分区方法可能会非常有用。