Content deleted Content added
m redirect bypass from Google maps to Google Maps using popups |
|||
Line 25:
{{main | Shortest path problem | Dijkstra's algorithm}}
One of the simplest and most common tasks in a network is to find the optimal route connecting two points along the network, with ''optimal'' defined as minimizing some form of cost, such as distance, energy expenditure, or time.<ref name="Worboys">{{cite book |last1=Worboys |first1=Michael |last2=Duckham |first2=Matt |title=GIS: A Computing Perspective |date=2004 |publisher=CRC Press |pages=211–218 |edition=2nd|chapter=5.7 Network Representation and Algorithms}}</ref> A common example is finding directions in a street network, a feature of almost any web street mapping application such as [[
In addition to the basic point-to-point routing, ''composite routing problems'' are also common. The [[Traveling salesman problem]] asks for the optimal (least distance/cost) ordering and route to reach a number of destinations; it is an NP-hard problem, but somewhat easier to solve in network space than unconstrained space due to the smaller solution set.<ref>{{cite web |title=v.net.salesman command |url=https://grass.osgeo.org/grass78/manuals/v.net.salesman.html |website=GRASS GIS manual |publisher=OSGEO |access-date=17 March 2021}}</ref> The [[Vehicle routing problem]] is a generalization of this, allowing for multiple simultaneous routes to reach the destinations. The [[Route inspection]] or "Chinese Postman" problem asks for the optimal (least distance/cost) path that traverses every edge; a common application is the routing of garbage trucks. This turns out to be a much simpler problem to solve, with [[polynomial time]] algorithms.
| |||