<p>There's a parallel algorithm for shortest paths from Carla Savage's 1977 Ph.D. thesis that consists of forming a square matrix with 0 on the diagonal entries, the length of the edges on the off-diagonal entries corresponding to edges, and a suitably large number for the remaining off-diagonal entries, and then repeatedly squaring this matrix in the <a href="http://en.wikipedia.org/wiki/Min-plus_matrix_multiplication">(min,+) algebra</a>.</p>

<p>After $\lceil\log_2 n\rceil$ squaring steps, the numbers in the resulting matrix are the distances between each pair of vertices. Each squaring step is easy to parallelize with logarithmic time and cubic work. So overall this algorithm takes $O(\log^2 n)$ time and $O(n^3\log n)$ work. With a little care (using a slightly more complicated algebra) this can be modified so that it also provides the first step of each shortest path in the same time and work bounds.</p>

<p>However, if you only want single source shortest paths rather than all pairs shortest paths, I don't know of anything that comes close to the total work of the sequential Dijkstra algorithm and that provides much in the way of a parallel speedup.</p>

CC BY-SA 2.5
2010-12-09T22:55:05.973Z
Thanks for the idea. But I use a slight variation of the  single source shortest path Dijkstra.
jutky
CC BY-SA 2.5
2010-12-10T03:04:44.517Z
Is what you are describing above the same as what was based on an idea of Steve Hedetniemi as described here?: http://highered.mcgraw-hill.com/sites/dl/free/0072880082/299355/Apps_Ch18.pdf  and also here:  http://deepblue.lib.umich.edu/handle/2027.42/59763
Joseph Malkevitch
CC BY-SA 2.5
2010-12-10T03:20:34.703Z
The matrix algebra part is the same, but the references you give don't seem to have the squaring trick for getting high powers of the matrix much more quickly than multiplying together n copies of the matrix. So they end up doing O(n^4) work, instead of closer to O(n^3) in Savage's version, and they're not as parallel.
David Eppstein
CC BY-SA 2.5
2010-12-10T04:36:04.387Z
Savage's algorithm is the natural parallelization of the Kleene-Roy-Floyd-Warshall algorithm: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
Jeffε
CC BY-SA 2.5
2010-12-09T22:45:40.667Z
2010-12-09T22:45:40.667Z
David Eppstein
<p>All-pairs shortest paths by repeated (min,+) matrix squaring is closely related to Floyd-Warshall, but they are not the same. In this respect, it is useful to think of Floyd-Warshall as (min,+) Gaussian elimination. Both approaches lend themselves to coarse-grained parallelisation, as discussed in <a href="http://dx.doi.org/10.1007/3-540-48224-5_15">http://dx.doi.org/10.1007/3-540-48224-5_15</a></p>

<p>The work required for repeated squaring can be improved from O(n^3 log n) to O(n^3) by the technique of <em>selective path doubling</em>, introduced by Alon, Galil and Margalit, and also discussed in the above paper.</p>

CC BY-SA 2.5
2010-12-20T21:31:52.707Z
2010-12-20T21:31:52.707Z
Alexander Tiskin
<p>I'd like to know what is the best method to parallelize the Dijkstra algorithm.</p>

<p>Thanks.</p>

CC BY-SA 2.5
2010-12-23T20:12:15.743Z
Try a literature search for parallel shortest path. You could start with e.g. "A Randomized Parallel Algorithm for Single-Source Shortest Paths" by Philip N. Klein and Sairam Subramanian in J. of Algorithms and papers citing it.
Warren Schudy
<ds.algorithms><graph-theory><graph-algorithms><dc.parallel-comp><shortest-path>
Dijkstra parallelization
jutky
# Dijkstra parallelization

(Asked by: username_0 on 2010-12-09)

I'd like to know what is the best method to parallelize the Dijkstra algorithm.

Thanks.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, dc.parallel-comp, shortest-path

> **Comments:**
> **username_1**: Try a literature search for parallel shortest path. You could start with e.g. "A Randomized Parallel Algorithm for Single-Source Shortest Paths" by Philip N. Klein and Sairam Subramanian in J. of Algorithms and papers citing it.  

---

## 2 answers

### Answer by username_2 on 2010-12-09. Score: 16

There's a parallel algorithm for shortest paths from Carla Savage's 1977 Ph.D. thesis that consists of forming a square matrix with 0 on the diagonal entries, the length of the edges on the off-diagonal entries corresponding to edges, and a suitably large number for the remaining off-diagonal entries, and then repeatedly squaring this matrix in the [(min,+) algebra](http://en.wikipedia.org/wiki/Min-plus_matrix_multiplication).

After $\lceil\log\_2 n\rceil$ squaring steps, the numbers in the resulting matrix are the distances between each pair of vertices. Each squaring step is easy to parallelize with logarithmic time and cubic work. So overall this algorithm takes $O(\log^2 n)$ time and $O(n^3\log n)$ work. With a little care (using a slightly more complicated algebra) this can be modified so that it also provides the first step of each shortest path in the same time and work bounds.

However, if you only want single source shortest paths rather than all pairs shortest paths, I don't know of anything that comes close to the total work of the sequential Dijkstra algorithm and that provides much in the way of a parallel speedup.

> **Comments:**
> **username_0**: Thanks for the idea. But I use a slight variation of the  single source shortest path Dijkstra.  
> **username_3**: Is what you are describing above the same as what was based on an idea of Steve Hedetniemi as described here?: http://highered.mcgraw-hill.com/sites/dl/free/0072880082/299355/Apps_Ch18.pdf  and also here:  http://deepblue.lib.umich.edu/handle/2027.42/59763  
> **username_2**: The matrix algebra part is the same, but the references you give don't seem to have the squaring trick for getting high powers of the matrix much more quickly than multiplying together n copies of the matrix. So they end up doing O(n^4) work, instead of closer to O(n^3) in Savage's version, and they're not as parallel.  
> **username_4**: Savage's algorithm is the natural parallelization of the Kleene-Roy-Floyd-Warshall algorithm: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm  

---

### Answer by username_5 on 2010-12-20. Score: 6

All-pairs shortest paths by repeated (min,+) matrix squaring is closely related to Floyd-Warshall, but they are not the same. In this respect, it is useful to think of Floyd-Warshall as (min,+) Gaussian elimination. Both approaches lend themselves to coarse-grained parallelisation, as discussed in <http://dx.doi.org/10.1007/3-540-48224-5_15>

The work required for repeated squaring can be improved from O(n^3 log n) to O(n^3) by the technique of *selective path doubling*, introduced by Alon, Galil and Margalit, and also discussed in the above paper.


---

