我试图找到数据集中两个节点之间的最短路径.我实现了dijkstra算法并使用它来证明给定两个节点(例如:Andrew_Card和Dick_Cheney),源和目标之间不存在路径.但是,我发现我的程序被操作系统杀死了.
调试后我发现问题可能与RAM中的资源分配有关.至于dijkstra算法,如果节点数n = 16,375,503,那么空间要求是
n*n = 16,375,503 * 16,375,503 > 10^{14}.
要在内存中运行此算法,我们至少需要
(10^{14} * 4) / (1024 * 1024 * 1024) = 10^5 GB (approximately equal)
of RAM.
因此,如果我们打算在内存中保留一个大的连通图,则无法使用dijkstra找到最短路径.如果我错了,请纠正我,因为我很长时间以来一直坚持这个？或者,如果可能有其他可能的原因我应该检查,那么请指出我.
我用C++实现了这个程序
边数= 25,908,132
kra*_*ich 14
如果边数相对较少(所有边可以适合主存储器),则可以使用邻接列表存储图形.它需要O(V + E)记忆,而不是O(V^2).此外,您可以将Dijkstra算法与优先级队列一起使用.它适用于稀疏图(它具有O(E log V)时间复杂性).对于具有关于2 * 10^7顶点和边缘的图形,这种方法应该可以正常工作(一个好的实现可以很容易地适应主存储器并运行不超过几分钟).