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?