An algorithm for finding shortest routes from all source nodes to a given destination in general networks

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 1/2M ( {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 ) 1/2N ( {N - 1} ) ( {N - 2} ) additions and comparisons.