An algorithm for finding shortest routes from all source nodes to a given destination in general networks
Jin Y. Yen · Quarterly of Applied Mathematics · 1970
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 {1}{2}M\left ( {N - 1} \right ) \\ \left ( {N - 2} \right ),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 {1}{2}N\left ( {N - 1} \right )\left ( {N - 2} \right ) additions and comparisons.