I try to understand the node ordering at contraction hierarchy.

To me, ordering and contracting node looks impossible because when contracting a node, then it influence the other node. Therefore, it looks impossible to calculate the exact node order.

Let me explain the node ordering.

According to the some parameters such as edge difference, we can order the node and put the node at the prioriry queue.

After ordering, we extract the minimum priority node.

Before contracting the node, we should compare its priority with the recomputed priority of the head of the node in the priority queue, assuming the node is contracted.

It is because the contracting behavior influence the order of the nodes.

In this case, I have a question. Is it possible we cannot extract any node in the priority queue?

For example, in the queue, there are the nodes A, B, C, D, E in the order.

When we extract the node A, we found node B is actual minimum node.

Therefore, we put node A in the queue, again and extract B.

But after that, we recomputed the priority node A, we get to know A is the minimum.

Then we have to put node B.

I think it can go on and on. Therefore we cannot contract any node.

Is my think reasonable? And then how can we design the algorithm of node ordering?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.