1

I've implemented a contraction-hierarchy routing system, which now works well, and I now need to add the stall-on-demand technique to speed it up; as explained here it can reduce the search space dramatically: over 25-fold in the example given.

However, I'm finding it hard to understand the few explanations I have found on the web, and the sample code given in the cited document lacks context.

I'd be grateful if anyone can point me to fuller and more carefully explained examples and code.

So far, I've found some code which is reasonably easy to understand in Christian Vetter's MoNav project. That partially answers my own question.

Graham Asher
  • 209
  • 1
  • 6

1 Answers1

1

For example, in the forward search v is the current vertex.

For an in-neighbor w of v (w→v) and w>v, such that edge w→v appears in the downward graph. If d(w)+c(w,v) < d(v), then w is a better candidate than v. So we don't have to expand on v in the forward search now.

Such influence can propagate to the neighbors of v in the upward graph, using the same "d(w)+c(w,v)+[c(v,x)] < d(x)" condition. The part in [c(v,x)] can expand deeper using BFS. However, these propagated stalled vertices can be unstalled if a shorter path to it is found.

When a vertex is stalled, you would not visit its neighbors, so the search space is reduced.

mako
  • 103
  • 2
superpig119
  • 11
  • 1