Content deleted Content added
No edit summary |
No edit summary |
||
Line 1:
In [[applied mathematics]], '''transit node routing''' can be used to speed up [[Shortest path routing|shortest-path routing]] by pre-computing connections between common access nodes to a sub-network relevant to long-distance travel<ref name=":0">{{Cite journal|last=Bast|first=H.|last2=Funke|first2=S.|last3=Sanders|first3=P.|last4=Schultes|first4=D.|date=2007-04-27|title=Fast Routing in Road Networks with Transit Nodes|url=http://dx.doi.org/10.1126/science.1137521|journal=Science|volume=316|issue=5824|pages=566–566|doi=10.1126/science.1137521|issn=0036-8075}}</ref>.
Transit node routing as a framework was established in 2007<ref name=":0" /> and many concrete implementations have surfaced in the years after such as approaches using grids, highway hierarchies<ref name=":1" /> and [[contraction hierarchies]]<ref name=":2" />. Transit node routing is a static approach that requires pre-processing of pair-wise distances between important nodes in the graph (see below how those nodes are chosen). A dynamic approach has not been published.<ref>{{Citation|last=Schultes|first=Dominik|title=Dynamic Highway-Node Routing|url=http://dx.doi.org/10.1007/978-3-540-72845-0_6|work=Experimental Algorithms|pages=66–79|publisher=Springer Berlin Heidelberg|isbn=9783540728443|access-date=2019-07-16|last2=Sanders|first2=Peter}}</ref>
__TOC__
| |||