MULTI-TERMINAL SHORTEST PATHS

Abstract

The present paper gives an algorithm that finds simultaneously the shortest paths between many pairs of nodes in a given network. In the book by Berge, the values of shortest paths between many pairs of nodes are found. Here, use is made of a special matrix multiplication technique to find the actual arcs that are used to form the shortest paths. In a network with n nodes, log sub 2 (n-1) special matrix multiplications are needed to find all the shortest paths. The present paper also gives an algorithm for constructing a network with prescribed shortest distances and with the total distances associated with arcs a minimum.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1965
Accession Number
AD0618757

Entities

People

  • T. C. Hu

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Contracts
  • Decomposition
  • Engineering
  • Governments
  • Interdisciplinary Science
  • Observation
  • Operations Research
  • Systems Science
  • Terminals
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.