{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T08:46:54Z","timestamp":1767084414222},"reference-count":12,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":10541,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1977,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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<jats:sup>2<\/jats:sup>). 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(\u221an) in the best case.<\/jats:p>","DOI":"10.1002\/net.3230070404","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T06:18:12Z","timestamp":1178864292000},"page":"323-334","source":"Crossref","is-referenced-by-count":93,"title":["A shortest path algorithm for grid graphs"],"prefix":"10.1002","volume":"7","author":[{"given":"F. O.","family":"Hadlock","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Graph Theory, An Algorithmic Approach","author":"Christofides N.","year":"1975"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"e_1_2_1_5_2","unstructured":"Hadlock F. O. \u201cMinimum Distance Minimum Turn Vehicle Routes \u201din preparation."},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"Hadlock F. O. \u201cPRIMS An Interactive System for the Design of Hybrid Circuit Layout \u201dProc. of the Third Annual Conference on Computer Graphics Interactive Techniques and Image Processing Philadelphia 1976 pp.293\u2013301.","DOI":"10.1145\/965143.563329"},{"key":"e_1_2_1_7_2","unstructured":"Hadlock F. O.andF.Hoffman \u201cBlock Patterns and Routing \u201dProc. of the Sixth Southeastern Conference on Combinatorics Graph Theory and Computing Boca Raton 1975 pp.385\u2013400."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1976.5009200"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1961.5219222"},{"key":"e_1_2_1_11_2","first-page":"114","volume-title":"Applied Graph Theory","author":"Marshall C. W.","year":"1971"},{"key":"e_1_2_1_12_2","first-page":"285","article-title":"The Shortest Path Through a Maze","volume":"30","author":"Moore E. F.","year":"1959","journal-title":"Annals of the Harvard Computation Laboratory"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1974.224054"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230070404","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230070404","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T09:51:30Z","timestamp":1699782690000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230070404"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,12]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1977,12]]}},"alternative-id":["10.1002\/net.3230070404"],"URL":"https:\/\/doi.org\/10.1002\/net.3230070404","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1977,12]]}}}