Content deleted Content added
Astenosfear (talk | contribs) |
m Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4 |
||
| (2 intermediate revisions by 2 users not shown) | |||
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|
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|
__TOC__
Line 33:
* How should local queries be handled?
The following example implementations of this framework answer these questions using different underlying methods such as grouping nodes in cells of an overlay [[Grid (spatial index)|grid]]<ref name=":1">{{Citation|
=== Geometrical approach using grids===
| |||