Query regarding dijkstra algorithm

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.

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).