4
$\begingroup$

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

$\endgroup$
5
$\begingroup$

Strictly speaking, the paper pointed out by singsumit handles the P2P shortest path problem (not the all pairs shortest paths problem).

If you really want to compute the all pairs shortest paths problem, I will recommend you to read these two papers.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

I tried to write a good implementation for precisely this problem, which is now available in Sage.

http://www.sagemath.org/doc/reference/sage/graphs/distances_all_pairs.html

While Sage is written in Python, this part is written in C so it can be expected to be very fast. This being said, your main problem is not about computing the distances but storing them. If you want to compute the distance between all pairs of vertices (100 000) and store it in memory, and assuming you are storing the distances on 32b=4B integers -- so be careful if you run a 64bits machine or if you should use floats instead -- you would need a total memory of about 20Gigs. That's already BIG if you planned to allocate this memory in a C array, it's a nightmare if you were thinking of Java and Integer objects.

Here's an idea that sometimes changes the view one can have one hard instances : you can recursively remove vertices of degree 1, because for each of them the "shortest path" goes through their only neighbor, so it is easy to remember at very small cost. With some luck it can reduce the size of your instance.

Nathann

$\endgroup$
  • $\begingroup$ Thanks! storage exactly is the problem. Basically the edge value shall update very frequently and system needs to re work regularly to update all the shortest paths. And because there are many factors such as: #lanes,traffic density,flow,blockades etc using a matrix would sadly be futile as it needs O(n^2) space and using objects would ease the job which again would add to space. research.ibm.com/trl/people/yanagis/papers/RT0882.pdf partly solved the problem, but far from over. Any other advice? $\endgroup$ – Jatin Jan 24 '12 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.