A note on the problem of updating shortest paths
- 1 September 1981
- Vol. 11 (3), 317-319
- https://doi.org/10.1002/net.3230110309
Abstract
The problem of updating shortest paths from all the vertices to a set of vertices when the length function is decreased was considered by S. Goto and A. Sangiovanni‐Vincentelli and a solution algorithm was presented based on the LU‐factorization of the measure matrix and a matrix inversion formula. The present paper shows that the problem can be solved by means of the Dijkstra method in a running time of the same order as Goto and Sangiovanni‐Vincentelli's algorithm, assuming a smaller amount of initial data than theirs, i.e., we do not need the LU‐factorization of the measure matrix.This publication has 6 references indexed in Scilit:
- A new shortest path updating algorithmNetworks, 1978
- Efficient Algorithms for Shortest Paths in Sparse NetworksJournal of the ACM, 1977
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- On some techniques useful for solution of transportation network problemsNetworks, 1971
- The parametric problem of shortest distancesUSSR Computational Mathematics and Mathematical Physics, 1968
- A note on two problems in connexion with graphsNumerische Mathematik, 1959