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'$.

  • $\begingroup$ This problem looks like NP-complete, it might be possible that there is no polynomial-time solution for this problem. $\endgroup$
    – ooo
    Commented Feb 4, 2020 at 10:49
  • 1
    $\begingroup$ 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/… $\endgroup$
    – Kuifje
    Commented Feb 4, 2020 at 11:00

1 Answer 1


In DP Bertsekas Network Optimization (that can be downloaded for free) there's an exercise at Page 104 (Finding an initial price vector) where you can find a method for solving shortest paths in dynamic graphs. Basically, it resorts to using the price vectors from the first iteration to warm start the method at the second. Many years ago I implemented that method to solve dynamic shortest paths on road problems under congestion. We used the price vectors given by the nominal speeds (in the absence of congestion) as starting price vectors. We saw that in a scenario of low or very local congestion, this warm start provided substantial speedups over the traditional approach of solving the SPP from scratch every time.

  • $\begingroup$ Thanks! I think this may be what I am looking for. Also, is your work on the road problems under congestion published somewhere? $\endgroup$ Commented Feb 4, 2020 at 15:12
  • $\begingroup$ It is in a working paper status ever since :-). My coauthor and I never took the time to wrap this up and eventually followed different paths and left it unfinished. $\endgroup$ Commented Feb 4, 2020 at 22:23
  • $\begingroup$ Lol, ok, no worries! Thank you anyway :) $\endgroup$ Commented Feb 5, 2020 at 15:31
  • $\begingroup$ I have also used warm start in a column generation setting with success. The problem with the added column is very similar to the problem at the previous step. Warm starting speeds up things significantly. $\endgroup$
    – nimcap
    Commented Feb 10, 2020 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.