AN APPRAISAL OF SOME SHORTEST PATH ALGORITHMS

Abstract

A critical review of the literature of shortest paths in networks that examines methods for determining (1) the shortest path between two specified nodes; (2) the shortest path between all pairs of nodes; (3) the second, third, etc., shortest path; (4) the fastest path through a network with travel times depending on the departure time; and (5) the shortest path between specified endpoints that passes through specified intermediate nodes. Inefficient algorithms, erroneous procedures, and false assumptions in the current literature are identified.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1967
Accession Number
AD0661265

Entities

People

  • S. E. Dreyfus

Organizations

  • RAND Corporation

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

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

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Mathematical Modeling and Probability Theory.