What is the time complexity of a* and bfs pathfinding?

Best case O(E) with a perfect heuristic. Worst case O(E log V). Space complexity is O(V). A* with an admissible heuristic is optimal; with h = 0 it is Dijkstra.

A* and BFS pathfinding

medium

BFS expands in rings; A* aims at the goal; greedy best-first charges at it and gets the answer wrong. Compare expanded-cell counts on the same maze - the heuristic is the only difference.

Best O(E) with a perfect heuristicWorst O(E log V)Space O(V)

Loading the a* and bfs pathfinding engine…

Where to go next

Breadth-first search

easy

Expands in rings, so it finds shortest paths.

Dijkstra's algorithm

medium

Settle the closest unvisited node, then relax its edges.

Rat in a maze

medium

Watch corridors light up and go dark again.