1970/01/01 by Jin Y. Yen · 285 citations
Computer Science · #Algorithm #Computer science #Data Management and Algorithms #Optimization and Search Problems #Theoretical computer science #Web Data Mining and Analysis
paper · pdf · doi:10.1090/qam/253822
published in Quarterly of Applied Mathematics 27(4), 526-530 (American Mathematical Society (AMS))
crossref issued 1970/01/01 · crossref published 1970/01/01 · crossref published-print 1970/01/01 · openalex publication_date 1970/01/01 · crossref created 2016/12/14 · openalex created_date 2025/10/10 · crossref deposited 2026/04/20 · openalex updated_date 2026/07/22 · crossref indexed 2026/08/05
This paper presents an algorithm for finding all shortest routes from all nodes to a given destination in N N -node general networks (in which the distances of arcs can be negative). If no negative loop exists, the algorithm requires 1 2 M ( N − 1 ) ( N − 2 ) , 1 > M N − 1 \frac 12M ( N - 1 ) ( N - 2 ),1 > MN - 1 , additions and comparisons. The existence of a negative loop, should one exist, is detected after 1 2 N ( N − 1 ) ( N − 2 ) \frac 12N ( N - 1 ) ( N - 2 ) additions and comparisons.