Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½ N ³ Additions and N ³ Comparisons

1 July 1972

journal article
Published by Association for Computing Machinery (ACM) in Journal of the ACM

Vol. 19 (3) , 423-424
https://doi.org/10.1145/321707.321712

Abstract

A (computer programming) algorithm is presented which is based on Dijkstra's principle for finding the lengths of all shortest paths from either a fixed node or from all nodes in N-node nonnegative-distance complete networks. This algorithm is more efficient than other available (computer programming) algorithms known to the author for solving the above two problems. An empirical study on a computer has confirmed its superiority.

Keywords

GRAPH AND NETWORK THEORY
SHORTEST NETWORK PATHS

This publication has 0 references indexed in Scilit:

Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½ N 3 Additions and N 3 Comparisons

Abstract

Keywords

Finding the Lengths of All Shortest paths in N -Node Nonnegative-Distance Complete Networks Using ½ N ³ Additions and N ³ Comparisons