The shortest path problem is one of the central problems in graph theory and algorithms. In the Replacement Path problem, we are given the source vertex s, the target vertex t, and theshortest path between them. The goal is to compute the cost of replacing each edge in this path - that is, for every edge ee on the shortest path, we must find the length of the shortest path from ss to tt that avoids ee.

We study this problem from a distributed perspective, where computational power and responsibility are distributed among the vertices. The algorithm presented will be in the CONGEST model.

This talk is based on my recently accepted work, Optimal Distributed Replacement Paths, accepted in PODC 2025, coauthored with Yi-Jun Chang, Yanyu Chen, Gopinath Misra, Hung Thuan Nguyen, and Bryce Sanchez.

The arXiv version of the paper can be found here: https://arxiv.org/pdf/2502.15378