All pair shortest path problem for large number of nodes I am having a small problem. I have the complete city's data which has over 100,000 nodes and 40,000 paths in my database. Now I need to calculate the all pair shortest path between all of them. 

Obviously running them all together will take a long long time to compute as the complexity being $\Theta(n^3)$. So what I have decided is that to divide all the nodes into 20 different circles. I will compute for each different circle and then merge all the table's using a small dynamic programming approach which has the complexity of $\Theta(n_1n_2)$

where $n_1$ i the number of nodes in 1st and $n_2$ in the 2nd circle. In my case $n_1$=$n_2$.

So this way I am running it in $O(n^3)$, but practically its much faster than before. Yet overall it still is taking a long long time to compute. Is there any better approach?
Or are there any better well known algorithms which can solve such problems faster?

Quite helpless
Search papers on : "Shortest Path Queries Using Highway Hierarchies". There is a paper by Sanders and Schultes. If you follow their citations, there are lot of other papers. These methods are very useful for real road networks.