To efficiently recalculate all-pairs shortest paths (APSP) after removing a node from a dense graph, the paper proposes a warm-start method that avoids recomputing the entire APSP matrix from scratch. By constructing a Need-Update-List, the algorithm identifies only the shortest paths affected by the removed node. If the cost of recalculation (based on affected paths) exceeds a threshold, the Floyd-Warshall algorithm is used; otherwise, Dijkstra’s algorithm selectively updates the affected paths. This approach reduces the recalculation complexity to O(n^2) in the best case, while the worst case remains O(n^3), achieving significant time savings compared to a full recalculation.
The paper:
https://arxiv.org/abs/2412.15122
Python code: