Breaking the Bellman-Ford Shortest-Path Bound

التفاصيل البيبلوغرافية
العنوان: Breaking the Bellman-Ford Shortest-Path Bound
المؤلفون: Elmasry, Amr
سنة النشر: 2024
المجموعة: Computer Science
مصطلحات موضوعية: Computer Science - Data Structures and Algorithms
الوصف: In this paper we give a single-source shortest-path algorithm that breaks, after over 65 years, the $O(n \cdot m)$ bound for the running time of the Bellman-Ford-Moore algorithm, where $n$ is the number of vertices and $m$ is the number of arcs of the graph. Our algorithm converts the input graph to a graph with nonnegative weights by performing at most $\min(2 \cdot \sqrt{n},2 \cdot \sqrt{m/\log n})$ calls to a modified version of Dijkstra's algorithm, such that the shortest-path trees are the same for the new graph as those for the original. When Dijkstra's algorithm is implemented using Fibonacci heaps, the running time of our algorithm is therefore $O(\sqrt{n} \cdot m + n \cdot \sqrt{m \log n})$.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2410.23383
رقم الانضمام: edsarx.2410.23383
قاعدة البيانات: arXiv