↑↓ move · ↵ open · esc close

← All algorithms/Finding a path

Greedy best-first search

Can I get there faster by heading straight for the goal?

Always expands the cell that looks closest to the goal. Fast when the way is open, but it can return a long path.

TimeO(V log V)
MemoryO(V)
Where it is usedPathfinding →
The idea

Greedy best-first search is Dijkstra’s algorithm with a different priority. Instead of the cost so far, it orders the frontier by a heuristic: an estimate of the distance still to go. It dives toward the goal.

On open ground this expands very few cells. Around an obstacle it pays for its single-mindedness: it keeps pushing at the wall that faces the goal, and the path it returns can be much longer than the shortest, because it never counts what it has already spent.

Try it

Loading the demo…

The grid with greedy best-first selected. Draw a wall right in front of the goal and watch it spend its effort against it.

Step by step
  1. 01Pick a heuristic h(cell): the straight-line, Manhattan or octile distance to the goal.
  2. 02Put the start in a priority queue ordered by h.
  3. 03Take the cell with the lowest h.
  4. 04If it is the goal, follow the stored parents back to the start.
  5. 05Otherwise queue each unvisited neighbour by its own h and repeat.
In pseudocode
function greedy_best_first(start, goal, h):
    parent = {start: none}
    heap   = [(h(start), start)]
    while heap is not empty:
        _, cell = heap.pop_min()
        if cell == goal: return path_from(parent, goal)
        for n in neighbours(cell):
            if n not in parent:
                parent[n] = cell
                heap.push((h(n), n))
    return no_path
What it costs
Time: O(V log V)Memory: O(V)

The worst case is the same as Dijkstra’s algorithm; in practice it often expands far fewer cells.

Strengths
  • Very few cells expanded on open ground.
  • A one-line change from Dijkstra’s algorithm.
Limits
  • Not optimal: the path can be much longer than the shortest.
  • Fooled by a dead end that faces the goal.
  • Only as good as the heuristic.
Where it is used
  • 01PathfindingCompare how few cells it expands with how long its path is, next to A* and Dijkstra.
Related algorithms

A*

Finding a path →

Dijkstra’s algorithm

Finding a path →