我正在寻找一种好方法来找到数十亿节点的网络(有向、循环、加权)中两点之间的最短路径。基本上我想要一种算法，即使最坏的情况很糟糕，通常也能非常快速地得到解决方案。
我对并行或分布式算法持开放态度，尽管它必须对数据集的大小有意义(在显卡上与 CUDA 配合使用的算法必须能够以 block 的形式进行处理) 。我不打算使用大量计算机来执行此操作，但可能最多使用几台计算机。
最佳答案
谷歌搜索会给你很多好的links 。第一个link它本身讨论了两种最短路径算法的并行实现。
在谈论 CUDA 上的实现时，您必须记住数十亿个节点 = 千兆字节的内存。这将对每张卡一次可以使用的节点(以获得最佳性能)进行限制。最大容量graphics card目前市场上的容量约为6GB。这可以让您估计可能需要使用的卡数量(不一定是机器数量)。
关于c - 全有或全无 - 快速启发式最短路径算法(并行？)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6314177/