Premium
A shortest path algorithm for grid graphs
Author(s) -
Hadlock F. O.
Publication year - 1977
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230070404
Subject(s) - shortest path problem , longest path problem , grid , widest path problem , distance , k shortest path routing , combinatorics , pathwidth , shortest path faster algorithm , computer science , path graph , mathematics , planar graph , indifference graph , algorithm , path (computing) , yen's algorithm , discrete mathematics , graph , dijkstra's algorithm , line graph , graph power , geometry , programming language
Grid graphs are a simple class of planar graphs for which the vertices can be assigned integer coordinates so that neighbors agree in one coordinate and differ by one in the other coordinate. Grid graphs arise in applications from the layout design of integrated circuits to idealized models of city street networks. In many applications, a shortest path between two given vertices is needed. The best known algorithms for the shortest path in a general graph of n vertices are of complexity 0(n 2 ). However, if edge lengths are of uniform length, the shortest path can be determined in time 0(n). In this paper, taking advantage of the concept of direction present in grid graphs, an algorithm is developed which is 0(n) in the worst case and 0(√n) in the best case.