So what we want is to contract nodes with small edge differences first.

Contracted Neighbors, I already talked about this.

We want to contract a node with small number of already contracted neighbors, so

that the nodes which we contract don't cluster in one place, but

they're actually spread out in all the regions of the graph.

Shortcut Covers, very important.

Basically it says how many nodes are there,

such that we cannot avoid visiting our node if we want to go to those nodes.

More formally, if we have some node, v, we can do the number of neighbors,

w of v, such that we have to create a shortcut, either to w or

from w in the case we need to contract v.

And this basically means that when we contract v,

we'll lose some shortest path to w.

And that's why we need to create an additional shortcut.

And so v is important for w, and if v is important for many, its neighbors,

then it's important.

And so, we need to first contract nodes with small importance,

with small shortcut cover.

Node level is an upper bound on the number of edges in the shortest

path from any node s to node v in the augmented graph.

It can be shown formally that this is an upper bound,

but I'll tell you the intuition.

So we initialize the level with 0.

And then when we contract some node v, we update the level of its neighbors.

So for a neighbor u of v, either we could get to u somehow without going through v,

and then contracting v doesn't influence its level.

Or we could go to u through node v.

But then to go to node v, we needed at most,

level of v edges, and then one more to get from v to u.

So that's why L(u) needs to be maximized by L(v) + 1.

So in the end, L(v) is an upper bound on the number of

edges on the shortest path to v.

And so we want to contract nodes with small level,

because first, we need to contract non-important nodes.

In the end we proposed the following importance measure.

We just sum up all those four values.

Note that this is a heuristic value, and you can actually play with weights of

those four quantities in the importance and see how preprocessing time and

query time change.

But we think that just summing them up will already work really well.

However, each of the four quantities is necessary for fast preprocessing and

queries.

If you avoid implementing at least one of them,

probably preprocessing or query time will be too long.

But then you can further optimize with the coefficients.

For example,

two times added distance plus three times contracted neighbors, and so on.

So it also means that you need to find a way to compute all of these

quantities efficiently at any stage of the preprocessing.

Both in the beginning, and also when you need to

contract a node but you've already contracted some other nodes.

This is not very hard and we'll leave this as an exercise to you.

So, we did a lot of work.

We've come up with a preprocessing stage.

We need a particular node ordering with that and

we've come up with a complex importance measure for nodes for that.

And also we need to do bidirectional Dijkstra, but

not classical bidirectional Dijkstra.

We need to do some tweaks in the query stage.

So, is it all worth it?

It turns out that yes, it is well worth it.

If we take for example, a graph of Europe with 18 million nodes, and

launch the classical Dijkstra's algorithm on it.

And we generate random pairs of vertices in different places of Europe and

then compute the shorter distances.

Then on average, it will work for 4.3 seconds.

However, if we launch Contraction Hierarchies on

the same graph with the same pairs of vertices and

we tweak the heuristics inside the contraction hierarchy as well.

It will work on average just for 18 milliseconds,

which is almost 25000 times faster.

So it is very well worth it.

For example, for a service like Google Maps or Yandex Maps,

working 25000 times faster means that you actually can provide

your service to millions of users and do it blazingly fast.

And the speed-up will only increase if you increase the size of a graph.

For example, if you go from the graph of Europe to the graph of the whole world,

the speed-up will only increase.