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

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.*
## No comments:

## Post a Comment