-2
$\begingroup$

Is there any situation that bidirectional search on a graph is not applicable? for example is there any classes of graph that we can only use ordinary Dijkstra's algorithm, and can not use its bidirectional variant.

The graph may be a dynamic graph.

$\endgroup$
3
$\begingroup$

Yes, a simple one is coming to my mind, a dynamic graph where the search operators are not reversible, i.e. both predecessors and successors of a node in the graph can not be calculated.

$\endgroup$
  • $\begingroup$ Thanks. Is there any resources to find more about such graphs. $\endgroup$ – moksef Mar 5 '16 at 13:56
  • 1
    $\begingroup$ Have a look to Principles of Artificial Intelligence (Nilsson 1980), a very good book. $\endgroup$ – FrankS101 Mar 5 '16 at 15:10
2
$\begingroup$

There are no such graphs.
If you have directed tree-like graph - it would make no sense to go from leaves, but... from the root it will work as intended, and from the leaves - it will stop there and wait to meet the previous.
It will be wasteful, but working. In given example, the same applies - it will produce output from one side, from the second it will stop on single vertex, so it will degrade to one-directional, therefore nothing makes bidirectional search unusable.
When you cannot perform search - it does not matter whether it was bidirectional or not, it will not wirk anyway.

$\endgroup$

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.