Roadnetworks
A roadnetwork 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 (i.e. highways). This property has been formalized using the notion of highway dimension. (research.microsoft.com/pubs/115272/soda10.pdf) 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. This phase may take several days for realistic data and some techniques. The second phase is the query phase. In this phase, source and target node are known. The running time of the second phase is generally less than a second. 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 USA in a fraction of a microsecond. (research.microsoft.com/pubs/142356/HL-TR.pdf). Other techniques that have been used are:
- ALT
- Arc Flags
- Contraction Hierarchies (http://www.springerlink.com/index/j062316602803057.pdf)
- Transit Node Routing
- Reach based Pruning
- Labeling
Read more about this topic: Shortest Path Problem