ITERATIVE METHODS FOR DETERMINING THE K SHORTEST PATHS IN A NETWORK
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.
- Pub. in Networks, v6 n3 p205-229 Jul 76.(PC A03/MF A01)
National Bureau of StandardsConnecticut Avenue at Van Ness Street, NW
Washington, DC United States 20008
- Shier, D R
- Publication Date: 1974-8-26
- Pagination: 26 p.
- TRT Terms: Linear equations; Mathematical models; Network analysis (Planning); Networks; Nodes (Networks); Telecommunications; Theorems; Theory; Transportation; Urban transportation
- Uncontrolled Terms: Network flows; Transportation models
- Old TRIS Terms: Linear algebraic equations; Nodes
- Subject Areas: Planning and Forecasting; Transportation (General);
- Accession Number: 00146668
- Record Type: Publication
- Source Agency: National Technical Information Service
- Report/Paper Numbers: Final Rpt.
- Files: TRIS
- Created Date: Feb 16 1977 12:00AM