Accession Number:

AD0618757

Title:

MULTI-TERMINAL SHORTEST PATHS

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Personal Author(s):

Report Date:

1965-04-01

Pagination or Media Count:

17.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE