<p>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.</p>

CC BY-SA 3.0
2012-01-19T18:33:43.637Z
2012-01-19T18:33:43.637Z
singhsumit
<p>I tried to write a good implementation for precisely this problem, which is now available in Sage.</p>

<p><a href="http://www.sagemath.org/doc/reference/sage/graphs/distances_all_pairs.html" rel="noreferrer">http://www.sagemath.org/doc/reference/sage/graphs/distances_all_pairs.html</a></p>

<p>While Sage is written in Python, this part is written in C so it can be expected to be <em>very</em> 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 <em>BIG</em> if you planned to allocate this memory in a C array, it's a nightmare if you were thinking of Java and Integer objects.</p>

<p>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.</p>

<p>Nathann</p>

CC BY-SA 3.0
2012-01-24T13:03:12.717Z
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. http://www.research.ibm.com/trl/people/yanagis/papers/RT0882.pdf partly solved the problem, but far from over. Any other advice?
Jatin
CC BY-SA 3.0
2012-01-23T13:49:58.540Z
2012-01-23T13:49:58.540Z
Nathann Cohen
<p>Strictly speaking, the paper pointed out by singsumit handles the P2P shortest path problem (not the all pairs shortest paths problem).</p>

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

<ul>
<li><p><a href="http://www.siam.org/proceedings/alenex/2007/alx07_004knopp.pdf">Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, Dorothea Wagner: Computing Many-to-Many Shortest Paths Using Highway Hierarchies. ALENEX 2007</a></p></li>
<li><p><a href="http://www.research.ibm.com/trl/people/yanagis/papers/IPDPS2010_yanagisawa.pdf">Hiroki Yanagisawa: A multi-source label-correcting algorithm for the all-pairs shortest paths problem. IPDPS 2010: 1-10</a></p></li>
</ul>

CC BY-SA 3.0
2012-01-20T04:20:28.577Z
2012-01-20T04:20:28.577Z
Snowie
<p>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. </p>

<p>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)$</p>

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

<p>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?</p>

<p>Quite helpless</p>

<ds.algorithms><graph-algorithms>
All pair shortest path problem for large number of nodes
Jatin
# All pair shortest path problem for large number of nodes

(Asked by: username_0 on 2012-01-19)

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

**Tags:** ds.algorithms, graph-algorithms


---

## 3 answers

### Answer by username_3 on 2012-01-20. Score: 6 | Accepted answer

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.

* [Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, Dorothea Wagner: Computing Many-to-Many Shortest Paths Using Highway Hierarchies. ALENEX 2007](http://www.siam.org/proceedings/alenex/2007/alx07_004knopp.pdf)
* [Hiroki Yanagisawa: A multi-source label-correcting algorithm for the all-pairs shortest paths problem. IPDPS 2010: 1-10](http://www.research.ibm.com/trl/people/yanagis/papers/IPDPS2010_yanagisawa.pdf)


---

### Answer by username_1 on 2012-01-19. Score: 6

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.


---

### Answer by username_2 on 2012-01-23. Score: 5

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

> **Comments:**
> **username_0**: 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. http://www.research.ibm.com/trl/people/yanagis/papers/RT0882.pdf partly solved the problem, but far from over. Any other advice?  

---

