Premium
Iterative methods for determining the k shortest paths in a network
Author(s) -
Shier D. R.
Publication year - 1976
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.3230060303
Subject(s) - shortest path problem , node (physics) , k shortest path routing , computer science , basis (linear algebra) , constrained shortest path first , analogy , mathematical optimization , average path length , mathematics , shortest path faster algorithm , algorithm , theoretical computer science , graph , engineering , linguistics , philosophy , geometry , structural engineering
This paper presents and develops an algebraic structure for determining the k shortest paths from a given node to all other nodes of a network. Three new methods for calculating such k shortest path information are examined and compared. These methods are based on a fairly strong analogy which exists between the solution of such network problems and traditional techniques for solving linear equations. On the basis of both theoretical and computational evidence, one of the three methods is seen to offer an extremely effective procedure for finding the k shortest paths from a given node in a network.