Updating of all the shortest paths
Takashi Izumi, Yutaka Takahashi, K. Kawanishi · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1989
Abstract There are times when updating of shortest paths is required when a part of a network structure, such as length of a branch, is altered. For updating shortest paths, information on already obtained shortest paths including mid‐progresses can be used. Many of the algorithms shown so far are aimed at altering the length of one branch in a network or some branches going in or out at a node. With these algorithms, it is necessary to repeat the application if there are simultaneous alterations of multiple branches other than described in the foregoing, and the efficiency is not always good in terms of computation steps. This paper describes an algorithm which updates shortest paths between all pairs of nodes when simultaneous alterations of lengths of multiple branches, with no restriction to branches going in/out at one node, are allowed. In terms of computation steps, our algorithm is more efficient than repeatedly applying conventional methods.