[Solved]: Bidirectional Dijkstra vs Dijkstra

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, tin V$ (from source and target respectively). Say there is a single path of length $ell$ from $s$ to $t$, $pilangle s, u_1, u_2, ldots, u_{ell-1}, trangle$. 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}$, $1leq 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 $pilangle s, u_1, u_2, ldots, u_{ell-1}, trangle$ 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,