AN APPRAISAL OF SOME SHORTEST-PATH ALGORITHMS

Abstract

The Memorandum discusses five discrete shortest-path problems: (1) determining the shortest path between two specified nodes of a network; (2) determining the shortest paths between all pairs of nodes of a network; (3) determining the second, third, etc. shortest path; (4) determining of the fastest path through a network with travel times depending on the departure time; and (5) finding the shortest path between specified endpoints that passes through specified intermediate nodes. Existing good algorithms are identified while some others are modified to yield efficient procedures. Also certain misrepresentations and errors in the literature are demonstrated.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1968
Accession Number
AD0693567

Entities

People

  • S. E. Dreyfus

Organizations

  • RAND Corporation

Tags

Communities of Interest

  • Counter IED
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Convergence
  • Determinants (Mathematics)
  • Digital Computers
  • Industrial Engineering
  • Iterations
  • Operations Research
  • Programming Languages
  • Terminals
  • Travel Time
  • United States

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Parallel and Distributed Computing.
  • Regression Analysis.