A Comment on Floyd's Algorithm for Shortest Chains.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1973
- Accession Number
- AD0762467
Entities
People
- Victor Klee
Organizations
- University of Washington