CoreSource checked

Greedy Best-First Search

Expands the node that appears closest to the goal by heuristic estimate.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Beginner
Family: Heuristic Search
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 5
Code example: Not ready
Visualization: Ready
Aliases: GBFS

Overview

Greedy Best-First Search uses only a heuristic score, so it can move quickly toward a goal but may miss the cheapest path.

Core Concepts

path costheuristic scoringgraph representationheuristic estimateheuristic searchroute costfrontier expansionpath reconstruction

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E)

Average

O(E)

Worst

O(E)

Space

O(V)

When to Use

Use Greedy Best-First Search when you need to rank frontier nodes by estimated remaining cost.
Use it for fast approximate navigation with inputs like graph or grid.
Use it when routes have explicit movement rules, costs, obstacles, or graph edges.
Use it when the Heuristic Search tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when edge costs or movement constraints do not match the algorithm's assumptions.
Avoid it when the required output is not found path.

What It Does

Ranks frontier nodes by estimated remaining cost
Expands the most promising-looking node

Use Cases

Fast approximate navigation
Puzzle search demos
Heuristic search teaching

Inputs

Graph or grid
Start and goal
Heuristic function

Outputs

Found path
No-path result

Key Formulas (1)

Greedy priority

priority(node) = h(node)

priority(node) = h(node)

Ranks frontier nodes only by estimated remaining distance.

Pseudocode

1.Put the start node in a priority queue
2.Prioritize nodes by heuristic distance to the goal
3.Expand the lowest-heuristic node
4.Add unvisited neighbors
5.Stop when the goal is reached

Canonical Example

Input: edges = A-B: 1, B-C: 2, A-C: 5; start = A; goal = C
Output: path = A -> B -> C, cost = 3
Explanation: Greedy Best-First Search: The algorithm compares route costs and selects the cheaper path through B.

Implementation Notes

Keep the input contract explicit: Graph or grid; Start and goal; Heuristic function.
Use this step as the implementation spine: Put the start node in a priority queue.
Then preserve the next state change: Prioritize nodes by heuristic distance to the goal.
Keep node ids, edge direction, and visited state explicit in the implementation.

Common Pitfalls

Greedy Best-First Search is not guaranteed to find the shortest path.
Not defining directed versus undirected edges clearly can change the result.
Treating a visited node as final before its best known cost is actually settled.
Handle empty, invalid, and boundary inputs before trusting found path.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show the search frontier pulled toward the goal by a heuristic.

Step 1 of 5: Put the start node in a priority queue

heuristic-frontier

Notes

Greedy Best-First Search operates in O(E) time and O(V) space within the Heuristic Search family. Key governing relation: priority(node) = h(node). Often compared with A* Search and Dijkstra's Algorithm.