2021/12/07 by JOAO MARCOS DUSI VILELA, Bruno Fanzeres, Vilela, João +5
Computer Science · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2112.04045
openalex publication_date 2021/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this article, we study the Adjacent Quadratic Shortest Path Problem (AQSPP), which consists in finding the shortest path on a directed graph when its total weight component also includes the impact of consecutive arcs. We provide a formal description of the AQSPP and propose an extension of Dijkstra's algorithm (that we denote aqD) for solving AQSPPs in polynomial-time and provide a proof for its correctness under some mild assumptions. Furthermore, we introduce an adjacent quadratic A* algorithm (that we denote aqA*) with a backward search for cost-to-go estimation to speed up the search. We assess the performance of both algorithms by comparing their relative performance with benchmark algorithms from the scientific literature and carry out a thorough collection of sensitivity analysis of the methods on a set of problem characteristics using randomly generated graphs. Numerical results suggest that: (i) aqA* outperforms all other algorithms, with a performance being about 75 times faster than aqD and the fastest alternative; (ii) the proposed solution procedures do not lose efficiency when the magnitude of quadratic costs vary; (iii) aqA* and aqD are fastest on random graph instances, compared with benchmark algorithms from scientific literature. We conclude the numerical experiments by presenting a stress test of the AQSPP in the context of real grid graph instances, with sizes up to 16 × 106 nodes, 64 × 106 arcs, and 109 quadratic arcs.