ALL SHORTEST ROUTES IN A GRAPH

Abstract

An inductive procedure on nodes is given that requires n(n-1)(n-2) comparison - addition operations to determine minimum routes between all nodes of a directed network. Arc distances may be negative. If negative cycles exist, however, termination will occur when one such is found.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1966
Accession Number
AD0646551

Entities

People

  • George Bernard Dantzig

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • California
  • Contractors
  • Contracts
  • Governments
  • Military Research
  • Nuclear Energy
  • Operations Research
  • Security
  • United States
  • United States Government
  • Universities

Fields of Study

  • Mathematics

Readers

  • Computer Networking
  • Electrical Engineering
  • Graph Algorithms and Convex Optimization.