Query regarding dijkstra algorithm

Question

I am trying to find shortest path between two nodes in a dataset. I implemented dijkstra algorithm and am using it to prove given two nodes (like: Andrew_Card and Dick_Cheney) there does not exist a path between the source and destination. However, I am finding that my program is getting killed by the operating system.

After debugging I found that the problem could be related to resource allocation in RAM. As for dijkstra algorithm, if the number of nodes, n=16,375,503, then the space requirement is

 n*n = 16,375,503 * 16,375,503 > 10^{14}. 

To run this algorithm in memory we need at least

(10^{14} * 4) / (1024 * 1024 * 1024) = 10^5 GB  (approximately equal)
of RAM.  

So, it is not possible to find the shortest path using dijkstra if we intend to keep a large connected graph in-memory. Please correct me if I am wrong as I am stuck on this since a long time? Or if there could be some other possible reason which I should check, then please point me to it too.

I implemented the program in C++

No. of edges=25,908,132

Answer 1

If the number of edges is relatively low(so that all edges can fit into main memory), you can just store the graph using adjacency list. It requires O(V + E) memory, instead of O(V^2). Moreover, you can use Dijkstra's algorithm with a priority queue. It works well for sparse graphs(it has O(E log V) time complexity). This approach should work fine for a graph with about 2 * 10^7 vertices and edges(a good implementation can easily fit into main memory and run for no more than several minutes).

Answer 2

If you need JUST the distance between two nodes, use something like A*.

But if you're doing all points shortest paths, then you're definitely stuck with O(n^2) space. You're finding O(n^2) answers - so you can't really do any better than having to store all of them.