title: Query regarding dijkstra algorithm
body: <p>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.</p>
  
  <p>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</p>
  
  <pre><code> n*n = 16,375,503 * 16,375,503 &gt; 10^{14}. 
  </code></pre>
  
  <p>To run this algorithm in memory we need at least</p>
  
  <pre><code>(10^{14} * 4) / (1024 * 1024 * 1024) = 10^5 GB  (approximately equal)
  of RAM.  
  </code></pre>
  
  <p>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.</p>
  
  <p>I implemented the program in C++</p>
  
  <p>No. of edges=25,908,132</p>