ALL SHORTEST ROUTES FROM A FIXED ORIGIN IN A GRAPH

Abstract

A shortest route is sought between a fixed origin to other nodes in a graph when directed arc distances are given which may be positive, negative, or zero. This problem as stated includes the difficult travelling salesman problem. A less difficult problem is considered instead, namely: To find a negative cycle in a graph if one exists or if none exists then to find all the shortest paths from the origin. The method is inductive on nodes.

Open PDF

Document Details

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

Entities

People

  • George Bernard Dantzig
  • M. R. Rao
  • W. O. Blattner

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

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

Fields of Study

  • Mathematics

Readers

  • Operations Research