5
$\begingroup$

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?)

$\endgroup$
6
$\begingroup$

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,

$\endgroup$
  • $\begingroup$ Thanks, that makes sense. So, for the domains, where in general, branching factor is same/close in both directions(like in road networks), can we say that on average, Bidirectional Dijkstra would perform better than Unidirectional Dijkstra? $\endgroup$ – a_123 May 8 '16 at 16:55
  • 1
    $\begingroup$ Absolutely and, indeed, if the branching factor is similar for both forward and backward search then Bidirectional Dijkstra is much faster than Unidirectional Dijkstra. However, we do not know yet how to recreate the same effect with A$^*$, i.e., when heuristics are considered. $\endgroup$ – Carlos Linares López May 8 '16 at 22:29
  • $\begingroup$ What do you think of the comparison between Bidirectional Dijkstra and A*? Which scenarios would support one over the other? $\endgroup$ – a_123 Sep 10 '16 at 3:05
  • $\begingroup$ So you mean to compare a brute-force search algorithm (bidirectional Dijkstra) with an informed heuristic search algorithm (A$ˆ*$). In general I would prefer the second unless the problem is very simple and the heuristic function is not very well informed. $\endgroup$ – Carlos Linares López Sep 10 '16 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.