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?