2
$\begingroup$

The problem concerns finding shortest paths in graph from a single source to a single destination.

So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* runs in expected time O(E), because It uses additional information to find the path faster.

Now let's simplify the problem and remove the weights. In an undirected and unweighted graph BFS runs in O(E+V), but can potentially be stopped earlier if a better solution is found.
Now consider some good heuristic is also available for the distance from any vertex to the destination - even though all edges have the same length (for example we are looking for a path on a grid composed of unit-length edges with obstacles on some edges).

The fact that such heuristic exists is (of course) some added information, and this added information should theoretically be usable to improve the running speed of the algorithm, but I was not able to find any methods that utilise this additional information to optimise how fast BFS runs. I believe the lower bound is still O(E), for example for a simple path, but the constant multiplier should probably be smaller.

I have searched Wikipedia for different methods and I came across Beam search and Best first search - but both utilise a queue, so in theory it bumps the computational complexity to that of Dijkstra.

To sum up - can some heuristic information be used to improve the runtime of BFS?

Improve this question
$\endgroup$
2
  • $\begingroup$ "both utilise a queue" > did you mean a priority queue? Because BFS itself uses a queue. $\endgroup$
    – Nathaniel
    May 17, 2022 at 23:02
  • $\begingroup$ A* is already that algorithm, since every directed-graph algorithm is also trivially an undirected-graph algorithm. However it does not have better expected time (in general), despite your claim. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    May 18, 2022 at 0:09

1 Answer 1

Reset to default
5
$\begingroup$

A$^*$ can be an improvement of BFS in some cases, for example when searching a path in a maze.

Coincidently, I am currently working on such graph traversal with my students. Here are some of the results. The first image is done with BFS (yellow are unsuccessfully explored parts of the maze, in green is the solving path), the second with A$^*$.

BFS A*

This answer may not be what you are looking for, because A$^*$ uses a priority queue, so the time complexity may be worse than BFS.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Even though it does use priority queue I believe it is really insightful to see an actual comparison. Thank You for this answer. And honestly the log(n) factor might not be that big in most cases. $\endgroup$
    – Karol Szustakowski
    May 18, 2022 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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