Accession Number : AD0762467

Title :   A Comment on Floyd's Algorithm for Shortest Chains.

Descriptive Note : Technical rept.,

Corporate Author : WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS

Personal Author(s) : Klee,Victor

Report Date : JUN 1973

Pagination or Media Count : 9

Abstract : Floyd's algorithm is an efficient method for finding all internodal distances in a directed network whose arc lengths may be negative hit in which there is no negative cycle. Under the latter assumption, the algorithm also determines the length of the shortest cycle through each node. Further, the algorithm can itself be used to test for the presence of negative cycles. However, the literature does not contain a careful discussion of Floyd's algorithm in the presence of negative cycles, and the purpose of the note is to supply one. (Author)

Descriptors :   (*NETWORKS, MATHEMATICAL MODELS), SET THEORY, ALGORITHMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE