Bidirectional Dijkstra vs Dijkstra

Question

Are there any kind of graphs where Bidirectional Dijkstra would expand more than Dijkstra?

I tried to come up with an argument like this:

Let node $n$ be expanded by Bidirectional Dijkstra. Now there are two possibilites:

1. Node $n$ was expanded in the forward search
2. Node $n$ was expanded in the backward search

If $n$ was expanded in the forward search, then it would have been expanded in Dijkstra's algorithm also because forward search of Bidirectional Dijkstra is essentially just Dijkstra stopped earlier.

If $n$ was expanded in the backward search, there are two cases possible:

1. $n$ is on the actual shortest path between start and goal.
2. $n$ is not on the shortest path between start and goal.

If $n$ is on the actual shortest path between start and goal, then $n$ will also be expanded by Dijkstra. If $n$ is not on the shortest path between start and goal, then $n$ might not be expanded by the Dijkstra.(I am not sure how to use this case. Does this suggest that Bidirectional Dijkstra can expand more nodes than Dijkstra?)

Answer 1

Absolutely yes! your arguments are correct. And, as matter of fact, it is very easy to come up with a graph where Bidirectional Dijkstra would expand more nodes than Unidirectional Dijkstra, following your reasoning.

Consider a graph $G(V, E)$ where $V$ is the set of vertices, $E$ is the set of edges and you want to find the shortest path between two vertices $s, t\in V$ (from source and target respectively). Say there is a single path of length $\ell$ from $s$ to $t$, $\pi\langle s, u_1, u_2, \ldots, u_{\ell-1}, t\rangle$. Let us assume further:

1. $s$ has only one descendant, $u_1$
2. And, in general, $u_i$ has only one descendant, $u_{i+1}$, $1\leq i<\ell - 1$

However, $t$ has many different descendants: $\{v_1, v_2, \ldots, v_k\}$. For the sake of clarity, let us assume without loss of generality that the cost of all edges is 1 and that the path $\pi\langle s, u_1, u_2, \ldots, u_{\ell-1}, t\rangle$ is the only optimal path.

Now, Bidirectional Dijkstra would expand first $s$ in the forward search and then $t$ in the backwards search. The forward OPEN list contains only $u_1$, whereas the backward OPEN list contains $\{v_1, v_2, \ldots, v_k\}$ and $u_{\ell-1}$. Next, $u_1$ is expanded in the forward search and the forward OPEN list only contains $u_2$. However, the backward search might choose $v_1$ for expansion. This is your case! $v_1$ does not belong to the optimal path, yet it is expanded by Bidirectional Dijkstra (admittedly, this depends on the tie breaking strategy but assume $k$ is too large and ties are broken randomly). In the end, the forward search would go all over $\pi$ whereas the backwards search might be entertained expanding descendants of nodes $v_i$.

However, the Unidirectional search algorithm would have gone all the way through $\pi$, as it is its only choice, finding the goal node in precisely $\ell$ expansions.

To prevent this, Ira Pohl's principle of cardinality is applied often. It dictates to expand nodes from the OPEN list with less nodes. In this case, it would suggest expanding only nodes from the forward search, making Bidirectional Dijkstra to behave like Unidirectional Dijkstra. However, it should not be very difficult to make some maths to find a little bit more involved case where Ira Pohl's principle of cardinality does not help and Bidirectional Dijkstra still expands more nodes than Unidirectional Dijkstra.

In general, we say that Bidirectional Dijkstra expands only $O(b^{d/2})$ nodes whereas Unidirectional Dijkstra has to expand $O(b^d)$ nodes, but this assumes that the branching factor is the same for the forward and backward search.

For a much broader discussion on the topic which also includes the intricacies of applying bidirectional search to heuristic search I do strongly recommend you reading: Robert C. Holte, Ariel Felner, Guni Sharon, Nathan R. Sturtevant. Bidirectional Search that is guaranteed to meet in the middle. AAAI 2016.

Hope this helps,