Premium
A new shortest path updating algorithm
Author(s) -
Goto S.,
SangiovanniVincentelli A.
Publication year - 1978
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230080406
Subject(s) - shortest path problem , algorithm , mathematics , path (computing) , set (abstract data type) , combinatorics , algebraic number , k shortest path routing , computer science , graph , mathematical analysis , programming language
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.