Realtime response of shortest path computation

Computing the shortest path between two locations in a network is an important and fundamental problem that finds applications in a wide range of fields. This problem has attracted considerable research interest and led to a plethora of algorithms. However, existing approaches have two main drawbacks: complete path computation before movement and re-processing when node failure occurs. In this paper, two novel algorithms, RSP (Realtime Shortest Path) and RSP+ (Realtime Shortest Path Plus), are proposed to handle both shortcomings. We perform a network pre-processing to ensure a constant time response of retrieving the shortest route for an arbitrary node to an important set of destinations. RSP+ further divides the complete path into smaller partial paths, which can then be computed in parallel. Besides, considering the continuous changes of the network, like traffic jams and road constructions, where certain paths are blocked, a fast recovery method to efficiently find the best alternative route is integrated into RSP+. Empirical studies have shown that RSP+ can achieve an average query processing time of 0.8 microseconds. Besides, the effectiveness of the recovery mechanism demonstrates that alternative routes can be obtained to avoid unavailable areas.