يك الگوريتم كوتاه‌ترين مسير پويا بر پايه الگوريتم مسير يابي تجزيه قطر كوتاه برنشتاين براي گراف هاي پر چگال

Abstract The Single-Source Shortest Path (SSSP) problem is one of the fundamental problems in graph theory an‎d algorithm design. It has a wide range of applications, including communication infrastructures an‎d transportation systems, an‎d has long been a central topic of research in computer science. Although classical algorithms developed for this problem are highly efficient, no tight lower bound on their running time has yet been established. Consequently, the search for faster an‎d more efficient algorithms remains an active area of research. Among the modern approaches proposed for this problem, the shortest-path algorithm based on low-diameter decomposition, introduced by Bernstein an‎d colleagues for graphs with negative edge weights, achieves improved time complexity compared to previous methods. Despite its rigorous theoretical analysis, however, a comprehensive experimental eva‎luation of its practical performance has not yet been conducted. Furthermore, this algorithm is built upon the concept of low-diameter decomposition an‎d consists of several modular components that fit together like pieces of a puzzle. Each component can be independently improved, leading to enhanced performance of the overall algorithm. One alternative version of the low-diameter decomposition algorithm is based on ran‎dom shifts. When substituted into the shortest-path algorithm, this version outperforms the original decomposition method. By introducing several modifications, it achieves significant improvements an‎d, in some cases, reduces execution time by up to an order of magnitude while delivering superior overall performance. On the other han‎d, in many practical applications, particularly transportation networks, the graph structure remains fixed while edge weights change over time. A common approach to designing dynamic algorithms is to transform a static algorithm into a dynamic one. Although dynamic variants have been developed for many classical shortest-path algorithms, no dynamic version of Bernstein’s low-diameter decomposition-based shortest-path algorithm has yet been proposed. In this research, after implementing the complete Bernstein algorithm, we introduce a dynamic version capable of han‎dling edge-weight updat‎es without requiring a full recomputation of the algorithm. The proposed method preserves the cost function an‎d shortest-path structure while utilizing information obtained during the initial execution. As a result, only the portions of the computation affected by the updat‎es are recomputed. The performance of the proposed dynamic algorithm was eva‎luated on graphs of varying sizes an‎d densities an‎d compared with both the static an‎d repeated-execution approaches. Experimental results demonstrate that, for most localized updat‎es, the proposed method significantly reduces execution time an‎d provides an efficient solution for dynamic graph environments. Keywords:Routing, Shortest Path, Low-Diameter Decomposition, Static Routing Algorithm, Dynamic Routing Algorithm

6 فصل

171290