A delay-Adaptive neural network for querying TOP-k critical vertices on time-Dependent shortest paths

This study proposes a delay-adaptive neural network (DANN) for querying the TOP-k critical vertices (kCV) on time-dependent shortest paths. Traditional kCV queries are typically formulated on static networks with fixed edge weights, whereas real-world network states often exhibit significant temporal dependencies. To address this challenge, this paper formally defines the mathematical model for kCV queries on time-dependent networks and designs a set of delay-adaptive neurons along with corresponding DANN operational mechanisms. According to the characteristics of the kCV query problem, delay-adaptive neurons are categorized into three types: source-peripheral neurons simulate source vertices and generate input information for the neural network; destination-peripheral neurons simulate destination vertices and output the kCV; intermediate neurons simulate other vertices and complete information reception, processing, and propagation. This approach offers several advantages: First, DANN is a weightless computational network with a physical network topology mapping structure that requires no training, demonstrating strong adaptability for kCV queries across time-dependent networks of varying scales and structures. Second, each component module of the delay-adaptive neuron has deterministic computational logic, essentially functioning as an information-processing unit composed of deterministic logic gates. Third, the DANN architecture endows neurons with parallel computing capabilities and a synchronization mechanism akin to chip clocks, significantly enhancing query response speed while ensuring the attainment of globally optimal solutions. Finally, this paper evaluates the algorithm’s performance through time-complexity analysis and correctness proofs. Comparative experiments conducted on real road network data against algorithms migrated from existing methods validate the effectiveness and advanced nature of the proposed approach.