Contraction hierarchies (part 3)

Formal definition of CH would be:

CH = (V, E'), "<", where V is set of nodes, E is set of edges of original graph with introduced shortcut edges and "<" is relation that defines different levels of contration hierarchy.

Levels/order of nodes in CH can be arbitrary. The main point is that shorcuts are introduced when necessary. To understand when shortcut is necessary, one has to understand the searching algorithm. Searching algorithm (bidirectional Dijkstra's algorithm) only relaxes edges that are connected to the nodes that are higher in CH than current node in one direction, and vice versa. That way, algorithm wouldn't find shortest paths and because of that we need to introduce new edges to the graph that represents existing shortest paths that algorithm don't takes into consideration. Not all shortest paths needs to be restored as new shortcut edges, it's enough to take in consideration adjacent nodes of some node that are higher in CH (sub-path of some shortest path is shortest path himself).




Algorithmically:

• add order/levels to the graph nodes
• for each node, respecting order, get it's adjacent nodes of higher order and find if shortest path between each pair of them goes through current node and if it is, add shortcut edge

Lets say that we take in cosideration just 2 adjacent nodes (from, in general, "n" of them):
  

 From this picture, if shortest path from v to w goes through node u that is lower in CH, new egde has to be added the CH graph so that shortest paths that searching algorithm takes in consideration are preserved.

Weight of new egde is equal to path distance from v to w.