A Comparison of Shortest Path Algorithms Applied to Sparse Graphs
USDOE, Bernie Hulme, USNRC, Sandia National Laboratories (SNL-NM), Albuquerque, NM (United States), John Wisniewski · 1978
Three methods are compared for finding shortest paths from one node to all other nodes in sparse, nonnegatively weighted, directed graphs. Dijkstra's method with a heap sort, Ford's method with a sequence list, and Yen's method are considered the best representatives of certain classes of methods for this problem. They have essentially the same storage requirements and are compared on the basis of algorithm execution time for a test set of randomly generated problems. For directed graphs that are sufficiently sparse, Ford's method with a sequence list is the fastest of the three methods. A different version of Ford's algorithm is proposed for use in the special case of undirected sparse graphs in order to make efficient use of the symmetry of the distance matrix.