A parallelization of Dijkstra's shortest path algorithm

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

The paper presents results concerning parallelization of Dijkstra's shortest path algorithm for directed graphs \(G=(V,E,W)\) with weighted edges. Selection of Dijkstra's algorithm for parallelization and getting positive results has not only practical meaning, the paper brings interesting ideas as well. Selection of the algorithm for parallelization was a very significant decision, since the Dijkstra's sequential algorithm does not seem to be the best candidate for parallelization. One can observe it, noting that it produces intermediate results (some paths) that are essential for the following steps. Moreover, small amount of computations performed in an elementary step makes a feeling that a parallelization can not help much in diminishing the running time of the algorithm. The main concept of the paper is the observation that the run of Dijkstra's algorithm can be partitioned into \(\sqrt[3]{n}\) phases for random graphs with high probability. The phases must be performed sequentially, but for each phase all the mentioned microsteps can be performed in parallel. In order to diminish the obvious communication problems the authors propose the implementation usage of shared memory CREW PRAM architecture and they investigate tables in order to store and to use the intermediate results. The authors present theoretical considerations getting signifficant improvement of asymptotic complexity of the algorithm, that is \(O(n^{\frac{1}{3}}\log n)\), while the sequential counterpart consumes time \(O(n\log n+m)\), \(n=| V|\) and \(m=| E|\). The authors claim the bound holds only for random graphs with high probability. Even more important are the results reported concerning simulations. The authors claim that the real average number of the phases was \(2.5\sqrt{n}\) for the OUT version of the algorithm, while for the version INOUT it was only \(6.0\sqrt[3]{n}.\) The authors do not mention the real parameters and arrangements for the simulation, so testing the algorithm using a real CREW PRAM machine seems to be important. The problem is still interesting for the authors, they inform about their future works concerning the possibility of improvements. For the entire collection see [Zbl 0895.00049].

Recommendations

Cited in

(17)

Describes a project that uses

Uses Software

GraphBase

This page was built for publication: A parallelization of Dijkstra's shortest path algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218150)