Hi. In this video, we will study the preprocessing phase for the contraction hierarchies algorithm. So the general idea is that we will be eliminating nodes of the initial graph, one by one, in some order. When we eliminate the node, some of the shortest paths that existed in the initial graph can be gone because they were passing through this node. And in this case, we will need to add some shortcuts so that we preserve the distances. Although the distances between any two nodes that are still in the graph are the same the distances between these nodes, in the initial graph. So we'll add some shortcuts some new edges to the graph. And in the end, we will get the augmented graph which has the same set of vertices as the initial graph. It also has all the edges of the initial graph. But apart from that it has all the added shortcuts as edges. This is the augmented graph. Basically the graph with augmented set of edges, and also we'll output the order of the nodes that we used in this preprocessing. This is the general scheme. Now how does the node contraction work? So let's look at this very simple line graph, all nodes in one chain. The nodes are numbered. And they are numbered already in the order in which we are going to contract the nodes in this example. And let's look what happens when we contract the nodes. So first, we contract node number one, it goes down, means that we contracted it. And actually what's on the top line is the graph, which is contracted. And now it is in green because it is already added into the augmented graph. And you see that there was a path from node 6 to node 4, which went through node 1. When we contracted it, it's no longer in the graph. So there is no path from 6 to 4 in this graph. And then we need to reconstruct that path. And so we add a new edge between 6 and 4, which is colored in blue in the picture. And the length of this edge should be equal to the length of the path between 6 and 4, which went through 1, because that was the only path. So it was the shortest path between 6 and 4. So we add a new edge of length 5 because the length of the shortest path between 6 and 4 was 5, and now after adding this edge it is again 5. And all the shortest path, all the distances between the nodes which are still in the graph on the top they are preserved. Now what happens when we contract node 2? Well nothing really happens because no shortest paths between the nodes which are left in the graph went through the node 2. So it's an interesting case. Now let's contract node 3. And again, there was the shortest path between 4 and 5 going through node 3, and it had length through each. So we add a new blue edge of length 3 directly between nodes 4 and 5. When we can track the node 4, it is the most interesting node because it already has two blue nodes. But nevertheless, when we contract it we remove the path between node 6 and 5, which runs through 4 through two blue edges. And we need to reconstruct the path. So we add a new edge directly between node 6 and 5 of length 8, because the path was of length 8. And notice that in the initial graph there was a path from 6 to 5, which went 6 to 1 to 4 to 3 to 5 and the total length was 3+2+1+2, which is 8. And now we just added one edge of length 8 between 6 and 5. And in the end we can track node 5. Nothing changes because no shortest paths between other vertices which are still in the graph which is basically only node 6 went through node 5. And we don't need to contract node 6 because it's the last node in the graph. And you see that the nodes in the new picture are different heights. And this just symbolizes that the higher is the node, the later it was contracted. And the higher the node, the more important it is. So we first contract or remove the least important nodes. And the nodes which are left in the end are the most important nodes. And we draw down from bottom to top in the order of increasing importance. Now let's see what happens in general when we contract node V. So, there can be some edges incoming into V from some nodes U1, U2 and maybe some others. There can be some edges outgoing from V. For example, two nodes W and W2 and maybe some others. Also there can be some undirected edges connect to V and then there will be both an incoming edge from the other ends to V and outgoing edge from V to the other end of this edges. And also, there could be directed edges from the same nodes to V and from V to this node. So some nodes can be both in the bottom part of the example and in the top bars of the example. But that doesn't really matter much, and we will discuss everything on this particular example. So what happens if V is contracted? Then V will be deleted, and the edges from U1 to V and from V to W1 will also be deleted. And let's suppose that this path from U1 to W1 of length 2, 1+1, was shortest in the initial graph. Then we will need to add a new edge directly from U1 to W1 so that we preserve the distances. So what would be the length of this edge? And the length of this edge will be of course 2 because the length of the new edge must be equal to the length of the corresponding incoming edge plus the length of the corresponding outgoing edge. And for every pair of edges, U1 to V, V to W1. Or U2 to V and V to W2, or U1 to V and v to W2. For each such pair, we need to add a new edge with a shortcut, but we don't have to add shortcuts always. So let's consider this another example, with nodes U2 and W2. There is this path from U2 to W2, going through V, of length 5, 3+2. However, it could happen so that there is another path from U2 to W2, which doesn't go through V, and has a length of just 3. Then, it is shorter than the path going through V. And then, if we delete node V, the shortest path from U2 to W2 doesn't change, because it doesn't go through V. And so in this case we don't have to add a shortcut. And in practice, we don't want to add a shortcut when we can avoid that. Because when we add a shortcut, we increase the number of edges in the preprocessed augment draft. And then our queries will work slow. Less edges, faster queries. So we really want to avoid adding shortcuts, and we need to find such paths, and such paths which don't go through the contracted node, and are shorter than the corresponding path going through the contracted node. They are called witness paths, because they are witnesses that we actually don't need to add a shortcut. And in the next video, we'll discuss how to efficiently search for those witness paths so that we don't have to add shortcuts in the preprocessing phase.