Analysis of the Weighted Graph Shortest Path Problem: Algorithms, Applications, and Challenges
DOI:
https://doi.org/10.61173/g9bj6p75Keywords:
Weighted Graph, Shortest Path Problem, Approximation AlgorithmsAbstract
In this paper, I will integrate what I have learned in the course to systematically review the concepts, challenges, and solutions involved in the shortest path problem. I will also introduce the applications and solutions of distributed algorithms to this problem. Moreover, based on the article ‘Distributed Approximation Algorithms for Weighted Shortest Paths’ that I have read, I will introduce the solutions for the single-source shortest path problem (SPP) from my understanding.
References
[1] Sun G.Z., Zhang Z., Yuan J. 2009. An efficient precomputation technique for approximation KNN search in road networks. In Proceedings of the 2009 International Workshop on Location Based Social Networks (LBSN ‘09). Association for Computing Machinery, New York, NY, USA, 41–44. https://doi. org/10.1145/1629890.1629899
[2] Danupon N. 2014. Distributed approximation algorithms for weighted shortest paths. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing (STOC ‘14). Association for Computing Machinery, New York, NY, USA, 565–573. https://doi.org/10.1145/2591796.2591850
[3] Christian S. Shortest-path queries in static networks, 2012. Submitted
[4] Christoph L., Boaz P. Fast routing table construction using small messages: extended abstract. In STOC, pages 381–390,
[5] Jeffrey D., Ullman., Mihalis Y. High-probability parallel transitive-closure algorithms. SIAM J. Comput., 20(1):100–125, 1991. 20, 21
Downloads
Published
Issue
Section
License
Copyright (c) 2023 by the authors.
This work is licensed under a Creative Commons Attribution 4.0 International License.
