Shortest paths in a lattice network: A comparative study

Network problems arise in many areas, but they are most commonly found in transportation and communication processes. A lattice network, with diagonal arcs, has characteristics that are common to a host of Euclidean transportation and communication networks. Such networks tend to be sparse and planar, with nodes that are generally adjacent to their nearest neighbors. This paper considers the problem of finding the shortest path between an origin and its destination in a lattice network with diagonal arcs. Dijkstra's algorithm and a modified version of Dijkstra's algorithm, which is more adaptive to network topology, are compared and computational results are included.