Shortest paths in a lattice network: a comparative study

Network problems arise in many areas, but they are most commonly found in t ransportation and communication processes, A lattice network, with diagonal arcs, has characteristics that are common to a host of Euclidean transport ation and communication networks. Such networks tend to be sparse and plana r, 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 alg orithm and a modified version of Djkstra's algorithm, which is more adaptiv e to network topology, are compared and computational results are included.