Shortest paths with euclidean distances: An explanatory model

Abstract This paper considers the problem of finding the shortest path between an origin and destination pair in networks whose arc lengths are Euclidean distances. Dijkstra's algorithm and a modified version of Dijkstra's algorithm which is more adaptive to network topology are compared. We demonstrate on the infinite lattice network with diagonal arcs (a prototype of more general sparse Euclidean networks) that on the average the adaptive algorithm expands less than 8.3% the area that would be expanded by the Dijkstra algorithm and in the worst case it expands less than 10.7%. In addition, we present computational results for more general networks.