A COMPARATIVE INVESTIGATION OF THE COMPUTATIONAL EFFICIENCY OF SHORTEST PATH ALGORITHMS

Abstract

Efficiency of shortest path algorithms is a function of various network parameters. This paper reports the results of an investigation of five algorithms for finding the shortest path from a root node to all other nodes for different network structures. Parameters considered are number of nodes, number of links, range of data (i.e., arc lengths), and shape (if applicable). It is hoped that the results will suggest to potential users of these algorithms which one is best suited for their problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1968
Accession Number
AD0685619

Entities

People

  • Lewis E. Hitchner

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Boundaries
  • California
  • Classification
  • Commerce
  • Computations
  • Computer Programming
  • Computer Programs
  • Computers
  • Contracts
  • Dynamic Programming
  • High Density
  • Low Density
  • Operations Research
  • Security
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.
  • Systems Analysis and Design