具有非负加权边的有向图中的所有对最短路径

Question

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

我需要计算所有对最短路径。这张图很大(20毫升的顶点和100毫秒的边)。弗洛伊德-沃尔是最好的算法吗？有一个好的库或工具来完成这个任务吗？

Answer 1

对于具有非负圈的有向图有向图有几种全到全部最短路径算法，Floyd- with可能是最著名的算法，但有了您给出的数字，我认为您在任何情况下都会遇到内存问题(时间可能是一个问题，但您可以找到可以轻松和大规模并行化的所有到所有算法)。

与您使用的算法无关，您必须将结果存储在某个地方。存储20,000,000平方公里=40万，000,000,000,000,000路径长度(如果不是完整路径本身)将使用数百兆字节，至少。

访问这些结果可能要比计算一条最短路径(内存墙)要长，这可以在不到一毫秒的时间内完成(取决于图形结构，您可以找到比Dijkstra或任何基于优先级队列的算法快得多的技术)。

我认为你应该寻找一种不需要计算所有到所有最短路径的替代方案，这样才是最诚实的。或者，研究图的结构(DAG，易于划分/聚类的结构化图，几何/地理信息.)为了应用不同的算法，因为在一般情况下，我看不到任何方法。

例如，对于您给出的数字，考虑到其维数，约5的平均度构成了一个适当的稀疏图。然后，图形分区方法可能非常有用。