So for example if we need to find the shortest path between node two and
node three in this graph, the path will look like this.
It will go first, by edges,
which go up to some node with the biggest importance.
For example, in this case, it will be node 6.
And then we'll go by edges down from that node 6, into node 3.
And to find such a path, we will use Bidirectional Dijkstra, which we'll start
both from 2 and from 3 and from 2 it'll go by forward edges which go up.
And from 3 it'll go by backward edges which also go up.
And then they will meet at some node and
we'll find some path which goes first up and then goes down.
This is the general idea but it is someone difference still
from the classical Bidirectional Dijkstra variant.
So in the Bidirectional Dijkstra as soon as we find some node that is process both
by the forward search and the backward search, we stop and
compute the shortest distance.
In this case, we don't stop when some node was processed by both searches.
We stop only when the extracted node is already farther
than our current estimate of the distance to the target.
This is the pseudo code code for the function ComputeDistance which takes as
inputs service node s and target node t and returns the distance between them.
Of course it also takes as input for example the graph and
the reverse graph for the bidirectional search but I just omitted those details.
Note however that you only need to store in the graph the edges which go upwards.
So we have a node A and a node B and an edge from A to B.
If A was contracted earlier than B, then you need to store this edge.
But if B was contracted earlier than A,
then this edge goes downwards and so you don't need to store this edge.
You can just delete it because it won't be used at all in the queries.
And so, you don't need to store it in the pre-process,
in the augmented graph at all.
We start with initializing variable estimate which will
store our current estimate of the distance between the source and the target.
And we initialize it with plus infinity because currently,
we don't know of any path between source and target.
Then we do the standard initialization of the bidirectional Dijkstra data.
We fill the arrays with distance estimates for the forward search and
the backward search with plus infinities.
And we'll also set the distance in the forward search from the source to zero.
And the distance in the backwards search from the target also to zero.
And also have the lists of the processed nodes for
the forward and the backward search.
Then we'll have the main loop and this loop goes while we still have some
nodes to process, either in the forward Dijkstra or in the backward Dijkstra.
Which means that basically in our priority queue that we use for
the Djikstra algorithm, there still are some nodes.
Either in the queue for the forward Djikstra search or in the queue for
the backward Djikstra search.