The all-pairs shortest path algorithms compute the shortest paths between all node pairs in a network. This paper presents a parallel algorithm for the all-pairs shortest path problem with a network decomposition approach. The algorithm decomposes the network into a set of independent augmented directed acyclic subnetworks that can be efficiently processed in parallel. The shortest path computation for each subnetwork provides a subset of the all-pairs shortest paths in the original network. The superiority of the new algorithm was verified through comparing its performance against that of the parallel single-origin shortest path algorithm. The execution times were compared for hypothetical and real-world networks with different sizes. A percentage of improvement in the execution time of about 50% was recorded for the transportation network of a large metropolitan area.
Get full access to this article
View all access options for this article.
References
1.
CormenT. H., LeisersonC. E., and RivestR. L.. Introduction to Algorithms. MIT Press, Cambridge, Mass., 1990.
2.
DijkstraE. W.A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, Vol. 1, 1959, pp. 269–271.
3.
MooreE.The Shortest Path Through a Maze. In Proceedings of the International Symposium on the Theory of Switching, Part II, Harvard University Press, Cambridge, Mass., 1957.
4.
FloydR. W.Algorithm 97: Shortest Path. Communications of the ACM, Vol. 5, No. 6, 1962.
5.
CarreA.An Algebra for Network Routing. Journal of the Institute of Mathematics and Its Applications, Vol. 7, 1971, pp. 273–294.
6.
JohnsonD. B.Efficient Algorithms for Shortest Paths in Sparse Networks. Journal of the ACM, Vol. 24, No. 1, 1977.
7.
DantzigG. B.All Shortest Routes in a Graph. In Theory of Graphs (RosenstiehlP., ed.), Gordon and Breach, New York, 1967.
8.
TabourierY.All Shortest Distances in a Graph. An Improvement to Dantzig’s Inductive Algorithm. Discrete Mathematics, Vol. 4, 1973, pp. 83–87.
9.
PapeU.Implementation and Efficiency of Moore Algorithms for the Shortest Route Problems. Math Programming, Vol. 7, 1974, pp. 212–222.
10.
RosenK. H.Discrete Mathematics and Its Applications, 5th ed. Addison-Wesley, Reading, Mass., 2003.
11.
ZiliaskopoulosA. K., MandanasF. D., and MahmassaniH. S.. An Extension of Labeling Techniques for Finding Shortest Path Trees. European Journal of Operational Research, Vol. 198, No. 1, 2009, pp. 63–72.
12.
FredmanM. L.New Bounds on the Complexity of the Shortest Path Problem. SIAM Journal on Computing, Vol. 5, 1976, pp. 83–89.
13.
KeltonW. D., and LawA. M.. A Mean-Time Comparison of Algorithms for the All-Pairs Shortest-Path Problem with Arbitrary Arc Lengths. Networks, Vol. 8, No. 2, 1978, pp. 97–106.
14.
AhujaK. K., MehlhornK., OrlinJ. B., and TarjanR. E.. Faster Algorithms for the Shortest Path Problem. Journal of the Association for Computing Machinery, Vol. 37, 1990, pp. 213–223.
15.
KleinP., RaoS., RauchM., and SubramanianS.. Faster Shortest-Path Algorithms for Planar Graphs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, New York, 1994, pp. 27–37.
16.
FlorianM.Applications of Parallel Computing in Transportation: Guest Editorial. Parallel Computing, Vol. 27, 2001, pp. 1521–1522.
17.
O’CearbhaillE. A., and O’MahonyM.. Parallel Implementation of a Transportation Network Model. Journal of Parallel and Distributed Computing, Vol. 65, No. 1, 2005, pp. 1–14.
18.
JungS., and PramanikS.. An Efficient Path Computation Model for Hierarchically Structured Topographical Road Maps. IEEE Transactions on Knowledge and Data Engineering, Vol. 14, No. 5, 2002, pp. 1029–1046.
19.
RajagopalanR., MehrotraK. G., MohanC. K., and VarshneyP. K.. Hierarchical Path Computation Approach for Large Graphs. IEEE Transactions on Aerospace and Electronic Systems, Vol. 44, No. 2, 2008, pp. 427–440.
20.
HribarM. R., TaylorV. E., and BoyceD. E.. Implementing Parallel Shortest Path for Parallel Transportation Applications. Parallel Computing, Vol. 27, No. 12, 2001, pp. 1537–1568.
BlewettW. J., and HuT. C.. Tree Decomposition Algorithm for Large Networks. Networks, Vol. 7, 1977, pp. 289–296.
23.
HabbalM. B., KoutsopoulosH. N., and LermanS. R.. A Decomposition Algorithm for the All-Pairs Shortest Path Problem on Massively Parallel Computer Architectures. Transportation Science, Vol. 28, No. 4, 1994, pp. 292–308.
24.
SongQ., and WangX.. Partitioning Graphs to Speed Up Point-to-Point Shortest Path Computation. In Proceedings of the 5th IEEE Conference on Decision and Control and European Control Conference, Orlando, Fla., 2011.
25.
SongQ., and WangX.. Efficient Routing on Large Road Networks Using Hierarchical Communities. IEEE Transactions on Intelligent Transportation Systems, Vol. 12, No. 1, 2011, pp. 132–140.
26.
FredericksonG. N.Planar Graph Decomposition and All Pairs Shortest Paths. Journal of the Association of Computing Machinery, Vol. 38, No. 1, 1991, pp. 162–204.
27.
AlonN., and GalilZ.. On the Exponent of the All Pairs Shortest Path Problem. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, 1991, pp. 569–575.
28.
CohenE.Efficient Parallel Shortest-Paths in Digraphs with Separator Decomposition. In Proceedings of the 19th Annual ACM Symposium on Parallelism, Parallel Algorithms and Architectures, Velen, Germany, 1993, pp. 57–67.
29.
KleinP., and SubramanianS.. A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica, Vol. 22, 1998, pp. 235–249.
30.
SolomonikE., BuluçA., and DemmelJ.. Minimizing Communication in All-Pairs Shortest Paths. In Proceedings of the IEEE 27th International Symposium on Parallel and Distributed Processing, Boston, Mass., 2013, pp. 549–559.
31.
KarypisG., and KumarV.. Multi-Level k-Way Partitioning Scheme for Irregular Graphs. Journal of Parallel and Distributed Computing, Vol. 48, 1998, pp. 96–129.
32.
TaylorV. E., HolmerB. K., and HribarE. J.. Balancing Load Versus Decreasing Communication: Exploring the Tradeoffs. Presented at the Hawaii Internal Conference on System Sciences, 1996.
33.
HendricksonB., and LelandR.. The Chaco Users’ Guide. Sandia National Laboratories, Albuquerque, N.M., 1993.
34.
HendricksonB., and LelandR.. A Multilevel Algorithm for Partitioning Graphs. Technical Report SAND92-1460. Sandia National Laboratories, Albuquerque, N.M., 1993.
35.
BarnardS. T., and SimonH. D.. A Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems. In Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing, 1993, pp. 711–718.
ZiliaskopoulosA., KotzinosD., and MahmassaniH. S.. Design and Implementation of Parallel Time-Dependent Least Time Path Algorithms for Intelligent Transportation Systems Applications. Transportation Research Part C, Vol. 5, No. 2, 1997, pp. 95–107.
