MULTI-TERMINAL SHORTEST PATHS
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Pagination or Media Count:
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.
- Operations Research