Deep Distance Sensitivity Oracles

Shortest path computation is one of the most fundamental and well-studied problems in algorithmic graph theory, though it becomes more complex when graph components are susceptible to failure. This research utilizes a Distance Sensitivity Oracle (DSO) for efficiently querying replacement paths in graphs with potential failures to avoid inefficiently recomputing them after every outage with traditional techniques. By leveraging technologies such as node2vec, graph attention networks, and multi-layer perceptrons, the study pioneers a method to identify pivot nodes that lead to replacement paths closely resembling optimal solutions with deep learning. Tests on real-world network demonstrate replacement paths that are longer by merely a few percentages compared to the optimal solution.