Article

Experimental analysis of dynamic all pairs shortest path algorithms

Authors:

Camil Demetrescu,

Stefano Emiliozzi,

Giuseppe F. ItalianoAuthors Info & Claims

SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 369 - 378

Published: 11 January 2004 Publication History

Abstract

We present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [18] and of Demetrescu and Italiano [7], and compare them to the dynamic algorithm of Ramalingam and Reps [25] and to static algorithms on random, real-world and hard instances. Our experimental data suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations.

References

[1]

D. Alberts, G. Cattaneo, and G. F. Italiano. An empirical study of dynamic graph algorithms. ACM Journal on Experimental Algorithmics, 2(5), 1997.]]

Digital Library

[2]

G. Amato, G. Cattaneo, and G. F. Italiano. Experimental analysis of dynamic minimum spanning tree algorithms. In Proc. SODA'97, pages 314--323, 1997.]]

Digital Library

[3]

Cattaneo, G. and Faruolo, P. and Ferraro-Petrillo, U. and Italiano, G. F. Maintaining dynamic minimum spanning trees: An experimental study. In Proc. ALENEX'02, 2002.]]

Digital Library

[4]

B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest paths algorithms: Theory and experimental evaluation. Math. Programming, 73:129--174, 1996.]]

[5]

C. Demetrescu, D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study. In Proceedings WAE'00, 2000.]]

Digital Library

[6]

C. Demetrescu and G. F. Italiano. Fully dynamic all pairs shortest paths with real edge weights. In Proc. FOCS'01, pages 260--267, 2001.]]

Digital Library

[7]

C. Demetrescu and G. F. Italiano. A new approach to dynamic all pairs shortest paths. In Proceedings of STOC'03, pages 159--166, 2003.]]

Digital Library

[8]

E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Math., 1:269--271, 1959.]]

[9]

S. Even and Y. Shiloach. An on-line edge-deletion problem. Journal of the ACM, 28:1--4, 1981.]]

Digital Library

[10]

B. Fortz and M. Thorup. Internet traffic engineering by optimizing OSPF weights. In Proceedings INFOCOM'00, pages 519--528, 2000.]]

[11]

M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their use in improved network optimization algorithms. Journal of the ACM, 34:596--615, 1987.]]

Digital Library

[12]

D. Frigioni, M. Ioffreda, U. Nanni, and G. Pasqualone. Analysis of dynamic algorithms for the single source shortest path problem. ACM JEA, 3, 1998.]]

Digital Library

[13]

D. Frigioni, T. Miller, U. Nanni, G. Pasqualone, G. Shaefer, and C. D. Zaroliagis. An experimental study of dynamic algorithms for directed graphs. In Proc. ESA'98, pages 320--331, 1998.]]

Digital Library

[14]

A. V. Goldberg. Shortest path algorithms: Engineering aspects. In Proc. ISAAC'01, 2001.]]

Digital Library

[15]

D. H. Greene and D. E. Knuth. Mathematics for the analysis of algorithms. Birkhäuser, 1982.]]

Digital Library

[16]

R. Iyer, D. R. Karger, H. S. Rahul, and M. Thorup. An experimental study of poly-logarithmic fully-dynamic connectivity algorithms. In B. E. Moret and A. V. Goldberg, editors, Proc. ALENEX'00, 2000.]]

[17]

D. Karger, D. Koller, and S. J. Phillips. Finding the hidden path: Time bounds for all-pairs shortest paths. SIAM Journal on Computing, 22(6):1199--1217, 1993.]]

Digital Library

[18]

V. King. Fully dynamic algorithms for maintaining allpairs shortest paths and transitive closure in digraphs. In Proc. FOCS'99, pages 81--99, 1999.]]

Digital Library

[19]

V. King and M. Thorup. A space saving trick for directed dynamic transitive closure and shortest path algorithms. In Proc. COCOON'01, pp. 268--277, 2001.]]

Digital Library

[20]

P. Loubal. A network evaluation procedure. Highway Research Record 205, pages 96--109, 1967.]]

[21]

J. Murchland. The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. Technical report, LBS-TNT-26, London Business School, Transport Network Theory Unit, 1967.]]

[22]

Paolo Narvaez, Kai-Yeung Siu, and Hong-Yi Tzeng. New dynamic algorithms for shortest path tree computation. IEEE/ACM Transactions on Networking, 8:734--746, 2000.]]

Digital Library

[23]

Paolo Narvaez, Kai-Yeung Siu, and Hong-Yi Tzeng. New dynamic SPT algorithm based on a ball-andstring model. IEEE/ACM Transactions on Networking, 9:706--718, 2001.]]

Digital Library

[24]

G. Ramalingam. Bounded incremental computation. In Lecture Notes in Computer Science 1089, 1996.]]

Digital Library

[25]

G. Ramalingam and T. Reps. An incremental algorithm for a generalization of the shortest path problem. Journal of Algorithms, 21:267--305, 1996.]]

Digital Library

[26]

J. Seward and N. Nethercote. Valgrind, an opensource memory debugger for x86-gnu/linux. URL: http://developer.kde.org/~sewardj/.]]

[27]

F. Zhan and C. Noon. Shortest path algorithms: An evaluation using real road networks. Transportation Science, 32(1):65--73, 1998.]]

Digital Library

Cited By

Greco SMolinaro CPulice CQuintana XSubrahmanian VRokne JKumar RCaverlee JTong H(2016)All-pairs shortest distances maintenance in relational DBMSsProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.5555/3192424.3192465(215-222)Online publication date: 18-Aug-2016
https://dl.acm.org/doi/10.5555/3192424.3192465
Greco SMolinaro CPulice C(2016)Efficient Maintenance of All-Pairs Shortest DistancesProceedings of the 28th International Conference on Scientific and Statistical Database Management10.1145/2949689.2949713(1-12)Online publication date: 18-Jul-2016
https://dl.acm.org/doi/10.1145/2949689.2949713
Chen YAcar UTangwongsan K(2014)Functional programming for dynamic and large data with self-adjusting computationACM SIGPLAN Notices10.1145/2692915.262815049:9(227-240)Online publication date: 19-Aug-2014
https://dl.acm.org/doi/10.1145/2692915.2628150
Show More Cited By

Experimental analysis of dynamic all pairs shortest path algorithms
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Experimental analysis of dynamic all pairs shortest path algorithms

We present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [1999] and of Demetrescu and Italiano [2006], and compare ...
A Multiple Pairs Shortest Path Algorithm

The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest ...
Solving all-pairs shortest path by single-source computations

Given an arbitrary directed graph G=(V,E) with non-negative edge lengths, we present an algorithm that computes all pairs shortest paths in time O(mn+mlgn+nT(m,n)), where m is the number of different edges contained in shortest paths and T(m,n) is the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms

January 2004

1113 pages

ISBN:089871558X

Program Chair:
Ian Munro

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 11 January 2004

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
905
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Greco SMolinaro CPulice CQuintana XSubrahmanian VRokne JKumar RCaverlee JTong H(2016)All-pairs shortest distances maintenance in relational DBMSsProceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.5555/3192424.3192465(215-222)Online publication date: 18-Aug-2016
https://dl.acm.org/doi/10.5555/3192424.3192465
Greco SMolinaro CPulice C(2016)Efficient Maintenance of All-Pairs Shortest DistancesProceedings of the 28th International Conference on Scientific and Statistical Database Management10.1145/2949689.2949713(1-12)Online publication date: 18-Jul-2016
https://dl.acm.org/doi/10.1145/2949689.2949713
Chen YAcar UTangwongsan K(2014)Functional programming for dynamic and large data with self-adjusting computationACM SIGPLAN Notices10.1145/2692915.262815049:9(227-240)Online publication date: 19-Aug-2014
https://dl.acm.org/doi/10.1145/2692915.2628150
Chen YAcar UTangwongsan KJeuring JChakravarty M(2014)Functional programming for dynamic and large data with self-adjusting computationProceedings of the 19th ACM SIGPLAN international conference on Functional programming10.1145/2628136.2628150(227-240)Online publication date: 19-Aug-2014
https://dl.acm.org/doi/10.1145/2628136.2628150
Weimann OYuster R(2013)Replacement Paths and Distance Sensitivity Oracles via Fast Matrix MultiplicationACM Transactions on Algorithms10.1145/2438645.24386469:2(1-13)Online publication date: 1-Mar-2013
https://dl.acm.org/doi/10.1145/2438645.2438646
Chen YDunfield JAcar U(2012)Type-directed automatic incrementalizationACM SIGPLAN Notices10.1145/2345156.225410047:6(299-310)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2345156.2254100
Chen YDunfield JAcar UVitek JLin HTip F(2012)Type-directed automatic incrementalizationProceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2254064.2254100(299-310)Online publication date: 11-Jun-2012
https://dl.acm.org/doi/10.1145/2254064.2254100
Chechik SLangberg MPeleg DRoditty L(2010)f-sensitivity distance Oracles and routing schemesProceedings of the 18th annual European conference on Algorithms: Part I10.5555/1888935.1888946(84-96)Online publication date: 6-Sep-2010
https://dl.acm.org/doi/10.5555/1888935.1888946
Shang SDeng KZheng K(2010)Efficient best path monitoring in road networks for instant local traffic informationProceedings of the Twenty-First Australasian Conference on Database Technologies - Volume 10410.5555/1862242.1862251(47-56)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1862242.1862251
Ding BYu JQin LMouaddib NValduriez PKemper ABouzeghoub MMarkl VAmsaleg LManolescu ITeubner J(2008)Finding time-dependent shortest paths over large graphsProceedings of the 11th international conference on Extending database technology: Advances in database technology10.1145/1353343.1353371(205-216)Online publication date: 25-Mar-2008
https://dl.acm.org/doi/10.1145/1353343.1353371
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents