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.

• Supplemental Notes:
  • Pub. in Networks, v6 n3 p205-229 Jul 76.(PC A03/MF A01)
• Corporate Authors:

  National Bureau of Standards

  Connecticut Avenue at Van Ness Street, NW
  Washington, DC  United States  20008
• Authors:
  • Shier, D R
• Publication Date: 1974-8-26

Media Info

• Pagination: 26 p.

Subject/Index Terms

• TRT Terms: Linear equations; Mathematical models; Network analysis (Planning); Network 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);

Filing Info

• 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