Friday 21 October 2011

Contraction hierarchies (part 4)

When preprocessing of original graphis is done, we need to build CH graph which consists of node order and original graph with shortcut edges introduced in preprocessing stage.

On CH graph we can make queries to find shortest paths with modified bidirectional Dijkstra's algorithm - algorthm performs forward search from starting node s expanding to the nodes that have higher order and backward search from target node t to the nodes that have lower order. If the shortest path exists, those two searches will meet at some node v. A shortest path from s to t consists from paths from s to v and from v to t.


The shortest paths found by this algorithm have particular form:


< s = u0, u1, ..., up = v, ..., uq = t >, p, q ∈ N

ui < ui+1 za i ∈ N, i < p 
uj > uj+1 za j ∈ N, p ≤ j < q
 A path found by a query is the shortest path because of preprocessing stage. In preprocessing stage we transformed graph introducing shortcut edges,which represents the shortest paths that algorithm does not take into consideration.

Now let's assume (for forward search, identical thing stands for backward search) that there exists a path that is shorter than the one we found with this algorithm:


So, let's say that at some point there exists a subpath that is shorter than path. Because algorithm expands towards nodes that have higher order, order of uk node must be lower than order of uk-1 and uk+1 nodes. Because of that fact, in preprocessing stage that path would be represented as shortcut edge with equal lenght and therefore, no such path that is shorter than the one algorithm found can exists.

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Hi, second paragraph says: (...)"and backward search from target node t to the nodes that have lower order".

    Then the formula says: uj > uj+1 za j ∈ N, p ≤ j < q

    I feel something is not quite right here. Maybe the formula should say "uj < uj+1"? Or maybe the paragraph should say "to the nodes that have higher order". I feel something is not quite clear in the explanation, but maybe I'm a bit lost.

    ReplyDelete