Reconfiguring Shortest Paths in Graphs


  • Kshitij Gajjar National University of Singapore, Singapore
  • Agastya Vibhuti Jha École polytechnique fédérale de Lausanne
  • Manish Kumar Ben-Gurion University of the Negev, Israel
  • Abhiruk Lahiri Ariel University, Israel



Planning, Routing, And Scheduling (PRS), Multiagent Systems (MAS)


Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time, so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) revamping road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c) and (d) are restrictions to different graph classes. We show that (a) is intractable, even for relaxed variants of the problem. For (b), (c) and (d), we present efficient algorithms to solve the respective problems. We also generalise the problem to when at most k (for some k >= 2) contiguous vertices on a shortest path can be changed at a time.




How to Cite

Gajjar, K., Jha, A. V., Kumar, M., & Lahiri, A. (2022). Reconfiguring Shortest Paths in Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 9758-9766.



AAAI Technical Track on Planning, Routing, and Scheduling