Greedy best-first

O(E log V)

Greedy best-first search is A* with the brakes off: it ranks open cells by the heuristic alone — the Manhattan distance straight to the goal — and ignores how far they already are from the start. That makes it very goal-directed and usually quick, expanding far fewer cells than BFS. The catch is that it's not optimal: by always chasing the cell that merely looks closest, it can commit to a route that detours around an obstacle the wrong way and finish with a longer path than A* would. It's the cautionary counterpart to A* — same machinery, but dropping the g term trades the optimality guarantee for speed.

Click a cell to toggle a wall
Grid
Edit the input and press Play

How it works

  1. Score each cell only by its heuristic distance to the goal.
  2. Always expand the open cell that looks closest to the goal.
  3. Add unseen free neighbours to the open set, remembering where they came from.
  4. Stop at the goal and trace back — the path may not be the shortest.

Pseudocode

1greedyBestFirst(grid, start, goal):  # O(E log V)2  open ← {start}3  while open not empty:4    cell ← node in open with least h    # h = manhattan(cell, goal)5    if cell = goal: stop6    for nbr in free neighbours(cell):7      if nbr not seen:8        prev[nbr] ← cell; add nbr to open9  walk prev from goal back to start     # NOT guaranteed shortest