Contraction hierarchies (part 2)

So, in general, there are two distinct phases: preprocessing of original graph (usually it takes more than a hour to finish) and queries (less than a second).


Contraction hierarchy is extreme case of hierarchy approach. Every node in the graph is represented as it's own level of hierarchy. This can be achieved in many ways, but one way is obvious and simple. If |N| is number of nodes in the graph, every node is enumerated from 1 to |N|. That way in hierarchy every node is represented as distinct level.


As searching algorithm, bidirectional Dijkstra's algorithm is used. It is classical Dijkstra's algorithm with some modifications. Algorithm searches from starting node in one direction and from ending node in other direction (this is classical bidirectional Dijkstra's algorithm), but it relaxes (see what relaxation is in Dijkstra algorithm pseudo-code) edges that are directed toward higher hierarchy nodes in one direction (essentially it expands towards higher hierarchy nodes) and edges that are directed toward lower hierarchy nodes in other direction. That way, searching algorithm wouldn't find shortest paths because it doesn't take in consideration shortest paths that aren't directed in a way algorithm searches. Because of that, all shortest path that are not directed properly have to be compensated in some way. This step is important because of validity of the algorithm.


So ... algorithm is bidirectional Dijkstra's algorithm. In one direction it relaxes edges that are directed towards nodes that are higher in the hierarchy (as I said, every node has it's own level in hierarchy) and opposite in other direction. Searching this way, not all shortest paths are taken into consideration and because of that algorithm would find inaccurate results. To restore shortest paths that aren't taken into consideration, a new edge is added to the graph. That edges are called shortcut edges and they represents existing shortest paths between two nodes in the graph.


(to be continued)