全双路最短路径问题的最快实现？

Question

我有一个加权图表30k节点160k边,没有负权重.我想计算从所有节点到其他节点的所有最短路径.我想我不能假设任何特定的启发式来简化问题.

我尝试使用这个Dijkstra C实现http://compprog.wordpress.com/2007/12/01/one-source-shortest-path-dijkstras-algorithm/,这是针对单个最短路径问题,调用函数dijkstras ()我所有的30个节点.你可以想象,这需要很长时间.目前我没有时间自己编写和调试代码,我必须尽快计算这些路径并将它们存储在数据库中,这样我就可以找到另一个更快的解决方案了,你有没有有小费吗？

我必须在最近的8GB内存的macbook pro上运行它,我想找到一个不超过24小时完成计算的解决方案.

非常感谢提前!!

欧亨尼奥

Answer 1

我查看了您在评论中发布的Dijkstra算法链接,我相信这是您效率低下的根源.在内部Dijkstra循环内部,它使用一种极其未经优化的方法来确定下一个要探索的节点(每个步骤对每个节点进行线性扫描).有问题的代码分为两个部分.第一个是此代码,它试图找到要操作的下一个节点:

mini = -1;
for (i = 1; i <= n; ++i)
    if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
         mini = i;

因为此代码嵌套在访问每个节点的循环内,所以复杂性(如链接中所述)为O(| V | ²),其中| V | 是节点数.在你的情况下,因为| V | 是30,000,整个循环将有9亿次迭代.这是非常缓慢的(正如你所见),但没有理由必须做这么多工作.

这里有另一个麻烦点,它试图找出图中哪个边缘应该用于降低其他节点的成本:

for (i = 1; i <= n; ++i)
   if (dist[mini][i])
       if (d[mini] + dist[mini][i] < d[i])
           d[i] = d[mini] + dist[mini][i];

这将扫描邻接矩阵中的整行,寻找要考虑的节点,这需要时间O(n),而不管有多少外出边缘离开节点.

虽然您可以尝试将此版本的Dijkstra修复为更优化的实现,但我认为这里的正确选择只是抛弃此代码并找到更好的Dijkstra算法实现.例如,如果您使用来自使用二进制堆实现的Wikipedia文章中的伪代码,则可以在O(| E | log | V |)中运行Dijkstra算法.在您的情况下,这个值刚刚超过200万,比您当前的方法快约450倍.这是一个巨大的差异,我愿意打赌,通过更好的Dijkstra实现,你最终会在比以前更短的时间内完成代码.

最重要的是,您可能需要考虑并行运行所有Dijkstra搜索,正如Jacob Eggers指出的那样.此凸轮可为您提供每个处理器的额外速度提升.结合上述(并且更为关键)修复,这可能会给您带来巨大的性能提升.

如果您打算在更密集的数据集(边数接近| V | ²/log | V |)上运行此算法,那么您可能需要考虑切换到Floyd-Warshall算法.每个节点运行一次Dijkstra算法(有时称为Johnson算法)需要时间O(| V || E | log | V |)时间,而使用Floyd-Warshall需要O(| V | ³)时间.但是,对于您提到的数据集,图表非常稀疏,因此运行多个Dijkstra实例应该没问题.

希望这可以帮助!

Answer 2

你的图有什么特殊的结构吗？该图是平面的（或接近平面的）吗？

我建议不要尝试存储所有最短路径，相当密集的编码（30k^2“下一步去哪里”条目）将占用 7 GB 内存。

有什么应用？当您需要找到特定的最短路径时，您确定执行双向 Dijkstra（或 A*，如果您有启发式）不够快吗？