2022/10/25 by Ziren Xiao, Ruxin Xiao, Xiao, Ziren +11 · 1 citation
Engineering · Computer Science · #Smart Parking Systems Research #Data Management and Algorithms #Transportation and Mobility Innovations
paper · pdf · doi:10.48550/arxiv.2210.14869
Dijkstra's algorithm is one of the most popular classic path planning algorithms, achieving optimal solutions across a wide range of challenging tasks. However, it only calculates the shortest distance from one vertex to another, which is hard to directly apply to the Dynamic Multi-Sources to Single-Destination (DMS-SD) problem. This paper proposes a modified Dijkstra algorithm to address the DMS-SD problem, where the destination can be dynamically changed. Our method deploys the concept of Adjacent Matrix from Floyd's algorithm and achieves the goal with mathematical calculations. We formally show that all-pairs shortest distance information in Floyd's algorithm is not required in our algorithm. Extensive experiments verify the scalability and optimality of the proposed method.