Editing Shortest path problem (section)

==Applications==
Shortest path algorithms are applied to automatically find directions between physical locations, such as driving directions on [[web mapping]] websites like [[MapQuest]] or [[Google Maps]]. For this application fast specialized algorithms are available.<ref>{{Cite web |title=Fast route planning |first=Peter |last=Sanders |author-link=Peter Sanders (computer scientist) |date=March 23, 2009 |url=https://www.youtube.com/watch?v=-0ErpE8tQbw |work=Google Tech Talk |archive-url=https://ghostarchive.org/varchive/youtube/20211211/-0ErpE8tQbw| archive-date=2021-12-11 |url-status=live}}{{cbignore}}</ref>

If one represents a nondeterministic [[abstract machine]] as a graph where vertices describe states and edges describe possible transitions, shortest path algorithms can be used to find an optimal sequence of choices to reach a certain goal state, or to establish lower bounds on the time needed to reach a given state. For example, if vertices represent the states of a puzzle like a [[Rubik's Cube]] and each directed edge corresponds to a single move or turn, shortest path algorithms can be used to find a solution that uses the minimum possible number of moves.

In a [[Computer network|networking]] or [[Telecommunications network|telecommunications]] mindset, this shortest path problem is sometimes called the min-delay path problem and usually tied with a [[widest path problem]]. For example, the algorithm may seek the shortest (min-delay) widest path, or widest shortest (min-delay) path.<ref>{{Cite book |chapter=K-Shortest Paths Q-Routing: A New QoS Routing Algorithm in Telecommunication Networks |first=S. |last=Hoceini |author2=A. Mellouk |author3=Y. Amirat |date=2005 |chapter-url=https://doi.org/10.1007/978-3-540-31957-3_21 |title=Networking - ICN 2005, Lecture Notes in Computer Science, Vol. 3421 |volume=3421 |pages=164–172 |publisher=Springer, Berlin, Heidelberg |doi=10.1007/978-3-540-31957-3_21 |isbn=978-3-540-25338-9 }}{{cbignore}}</ref>



A more lighthearted application is the games of "[[six degrees of separation]]" that try to find the shortest path in graphs like movie stars appearing in the same film.

Other applications, often studied in [[operations research]], include plant and facility layout, [[robotics]], [[transportation]], and [[Very-large-scale integration|VLSI]] design.<ref>{{cite journal |doi=10.1145/242224.242246 |title=Developing algorithms and software for geometric path planning problems |date=December 1996 |first=Danny Z. |last=Chen |journal=ACM Computing Surveys |volume=28 |issue=4es |s2cid=11761485 |at=Article 18 }}</ref>

===Road networks===
A road network can be considered as a graph with positive weights. The nodes represent road junctions and each edge of the graph is associated with a road segment between two junctions. The weight of an edge may correspond to the length of the associated road segment, the time needed to traverse the segment, or the cost of traversing the segment. Using directed edges it is also possible to model one-way streets. Such graphs are special in the sense that some edges are more important than others for long-distance travel (e.g. highways). This property has been formalized using the notion of highway dimension.<ref>Abraham, Ittai; Fiat, Amos; [[Andrew V. Goldberg|Goldberg, Andrew V.]]; Werneck, Renato F. [http://research.microsoft.com/pubs/115272/soda10.pdf%20research.microsoft.com/pubs/115272/soda10.pdf "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms"]. ACM-SIAM Symposium on Discrete Algorithms, pages 782–793, 2010.</ref> There are a great number of algorithms that exploit this property and are therefore able to compute the shortest path a lot quicker than would be possible on general graphs.

All of these algorithms work in two phases. In the first phase, the graph is preprocessed without knowing the source or target node. The second phase is the query phase. In this phase, source and target node are known. The idea is that the road network is static, so the preprocessing phase can be done once and used for a large number of queries on the same road network.

The algorithm with the fastest known query time is called hub labeling and is able to compute shortest path on the road networks of Europe or the US in a fraction of a microsecond.<ref>Abraham, Ittai; Delling, Daniel; [[Andrew V. Goldberg|Goldberg, Andrew V.]]; Werneck, Renato F. [http://research.microsoft.com/pubs/142356/HL-TR.pdf research.microsoft.com/pubs/142356/HL-TR.pdf "A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks"]. Symposium on Experimental Algorithms, pages 230–241, 2011.</ref> Other techniques that have been used are:

* ALT ([[A* search]], landmarks, and [[triangle inequality]])
* Arc flags
* [[Contraction hierarchies]]
* [[Transit node routing]]
* Reach-based pruning
* Labeling
* [[Hub labels]]