A new shortest path updating algorithm

A new algorithm for updating shortest paths from all vertices to a set of vertices following a decreasing‐length‐modification of some arcs, is presented. The algorithm is based on a formula which has an algebraic analogy with the well‐known Householder formula for inverting modified matrices. The number of operations (i.e., additions and comparisons) required for solving the modified shortest path problem is estimated as 0(mn 2 ), where n is the overall number of vertices and m is a parameter related to the arcs which have been updated. The algorithm proposed here is particularly powerful for solving large‐scale networks with sparse structure.