Contraction hierarchies (part 1)

And now something completely different. :)



"Contraction hierarchies" is new approach for solving shortest path problem in graph theory. Shortest path problem (http://en.wikipedia.org/wiki/Shortest_path_problem) can be solved using classical algorithms like Dijkstra's algorithm (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). But, classical algorithms are not useful on large graphs (more than 10 000 nodes). Today's roads networks are represented as a graph with about 10 million nodes or more and algorithm is implemented on small devices (navigation devices, mobile devices, ...) which have limited computing power. A problem with classical algorithms is their speed of finding shortest path on large graphs and space required for running of the algorithm. That's why they're not practical even on fast computers - they can't finish finding shortest path on large graphs due to large space consumption. There have been many speedup techniques for finding shortest path in large graph and they are more or less successful in that task.

In general, speedup tehniques have two distinct phases: preprocessing of original graph and queries for finding shortest path. In preprocessing phase some information is extracted from graph and it's being used in query phase to speedup finding of the shortest path.

Modern navigational devices generally use some kind of modified (bidirectional) A* algorithm (http://en.wikipedia.org/wiki/A*_search_algorithm) with hierarchical approach. That means that graph is devided according to node/road importance (local road, highway, ...) in preprocessing phase and then searching algorithm uses hierarchy to speedup finding of the shortest path (basic idea is that highway road is "faster" than local road). A problem with this approach is that there is no formal definition what highway is and what local road is (humans are manually doing that). Because of that errors are possible.
Also, searching algorithm is optimized in a way that it makes trade-off between speed and accuracy.


For that reasons new algorithms are reseached that are fast on large graphs and that give exact results.


(to be continued)