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  USA  20008
  • Authors:
    • Shier, D R
  • Publication Date: 1974-8-26

Media Info

  • Pagination: 26 p.

Subject/Index Terms

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