# Re-calculating shortest path in slightly altered graph

I was wondering if someone has come across this before and/or has a smart idea for the following:

I have a directed graph $$G$$ with costs $$c$$ associated with the arcs, and I know the shortest path $$P^G_{st} = \{s,\dots,i,j,\dots,t\}$$ in $$G$$ between nodes $$s$$ and $$t$$. Is there an efficient way to determine the shortest path between $$s$$ and $$t$$ in graph $$G'$$, which is equal to $$G$$ with the exception of the cost of a single arc $$(i,j)$$ in $$P^G_{st}$$ that is now $$c'_{ij} = c_{ij} + \alpha, \alpha > 0$$? By "efficient" I mean something better than re-calculating from scratch the complete shortest path in $$G'$$.

• This problem looks like NP-complete, it might be possible that there is no polynomial-time solution for this problem. – ooo Feb 4 at 10:49
• So what you are looking for is sensitivity analysis. There are many papers that tackle this, including without linear programming. See for example researchgate.net/publication/… – Kuifje Feb 4 at 11:00