Graph Heuristics

12 min read • Assignment

Graph Heuristics

Greedy BFS • Dijkstra's • A*

A graph heuristic is a strategy for deciding which node to explore next when searching through a graph. The three algorithms in this lesson each make that decision differently — trading off speed, memory, and optimality.

Greedy BFS

Uses only h(n) — the estimated cost to goal. Fast but not guaranteed optimal.

Dijkstra's

Uses only g(n) — the actual cost from start. Optimal but explores in all directions.

Uses f(n) = g(n) + h(n) — combines both. Optimal and efficient. Used in the Maze Runner.

Work through the sidebar from left to right. Pass the quiz for each algorithm to unlock the next.

Algorithm Journey

Pass each quiz to unlock the next algorithm.

Game Status: Not Started

Select an algorithm in the sidebar to begin. Complete each quiz to unlock the next.
Use the Maze Runner on the right to see these algorithms in action!

Greedy Best-First Search

Greedy Best-First Search expands the node that appears closest to the goal using only a heuristic function h(n). It never looks back at how far it has already traveled — only at how far it thinks it needs to go.

Core idea

At every step, look at all available nodes and pick the one with the smallest h(n) (estimated distance to goal). This is "greedy" because it commits immediately to what looks best right now.

Algorithm steps

Add the start node to the open list (priority queue sorted by h(n))
Pop the node with the lowest h(n)
If it's the goal — done. Otherwise mark it visited
Add all unvisited neighbors to the open list
Repeat from step 2

Key properties

Property	Greedy BFS
Uses	`h(n)` only — estimated cost to goal
Complete?	No — can loop in graphs with cycles
Optimal?	No — ignores actual edge costs
Time	O(b^m) worst case
Space	O(b^m) worst case

Why it can fail

The heuristic is just an estimate. Greedy can take a path that looks short but is actually expensive. In the code below, the graph has two paths to the goal:

A → C → G: Greedy picks this (C has lower h) — total cost 9
A → B → G: Optimal path — total cost 5

Greedy chose wrong because it only saw the heuristic, not the edge weights.

AP Exam tip: On the AP CSA exam, Greedy algorithms appear in the context of locally optimal choices that don't guarantee a globally optimal solution. Know that Greedy ≠ optimal.

Code Runner Challenge

Greedy Best-First Search

View IPYNB Source

// CODE_RUNNER: Greedy Best-First Search

import java.util.*;

public class Main {

    static class Node {
        String name;
        int heuristic; // estimated distance to goal
        List<int[]> neighbors = new ArrayList<>(); // [neighborIndex, edgeCost]

        Node(String name, int heuristic) {
            this.name = name;
            this.heuristic = heuristic;
        }
    }

    public static void main(String[] args) {
        // Build graph: A(h=10) -> B(h=5), C(h=3); B -> G(h=0); C -> G(h=0)
        Node a = new Node("A", 10);
        Node b = new Node("B", 5);
        Node c = new Node("C", 3);
        Node g = new Node("G", 0);
        Node[] nodes = {a, b, c, g};

        a.neighbors.add(new int[]{1, 2}); // A->B cost 2
        a.neighbors.add(new int[]{2, 8}); // A->C cost 8
        b.neighbors.add(new int[]{3, 3}); // B->G cost 3
        c.neighbors.add(new int[]{3, 1}); // C->G cost 1

        // Greedy BFS: always pick the neighbor with lowest h(n)
        Set<String> visited = new HashSet<>();
        PriorityQueue<Integer> open = new PriorityQueue<>(
            Comparator.comparingInt(i -> nodes[i].heuristic)
        );

        open.add(0); // start at A
        Map<Integer, Integer> parent = new HashMap<>();
        parent.put(0, -1);

        System.out.println("=== Greedy BFS Traversal ===");
        int goalIdx = -1;
        while (!open.isEmpty()) {
            int curr = open.poll();
            if (visited.contains(nodes[curr].name)) continue;
            visited.add(nodes[curr].name);
            System.out.println("Visiting: " + nodes[curr].name + " (h=" + nodes[curr].heuristic + ")");

            if (nodes[curr].heuristic == 0) { goalIdx = curr; break; }

            for (int[] edge : nodes[curr].neighbors) {
                if (!visited.contains(nodes[edge[0]].name)) {
                    open.add(edge[0]);
                    if (!parent.containsKey(edge[0])) parent.put(edge[0], curr);
                }
            }
        }

        // Reconstruct path
        System.out.print("\nPath found: ");
        List<String> path = new ArrayList<>();
        int p = goalIdx;
        while (p != -1) { path.add(nodes[p].name); p = parent.get(p); }
        Collections.reverse(path);
        System.out.println(String.join(" -> ", path));

        System.out.println("\nNotice: Greedy chose C (h=3) over B (h=5) — lower heuristic!");
        System.out.println("Greedy path cost: 8 + 1 = 9");
        System.out.println("Optimal path cost: 2 + 3 = 5  (A->B->G)");
        System.out.println("Greedy is NOT optimal — it ignored actual edge costs.");
    }
}
Main.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Knowledge Check: Greedy BFS

Q1. Greedy BFS selects the next node based on...

a) The smallest g(n) — actual cost from start b) The smallest h(n) — estimated cost to goal c) f(n) = g(n) + h(n) d) Random neighbor selection

Q2. Which statement about Greedy BFS is true?

a) It always finds the shortest path b) It considers actual path costs c) It may find a suboptimal path if the heuristic is misleading d) It is guaranteed to be complete in all graphs

✅ Dijkstra's Algorithm unlocked! Click it in the sidebar to continue.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source node to every other node in a weighted graph. Unlike Greedy BFS, it tracks the actual cost traveled — not just an estimate.

Core idea

Maintain a running cost g(n) for each node — the cheapest known path from the start. Always expand the node with the smallest current g(n). When a cheaper route to a neighbor is found, update it.

Algorithm steps

Set g(start) = 0, set all other nodes to g = ∞
Add start to a min-priority queue (sorted by g)
Pop the node with the smallest g(n) — call it current
For each neighbor: compute tentative = g(current) + edge_cost
If tentative < g(neighbor), update and re-add to queue
Mark current as settled. Repeat from step 3

Key properties

Property	Dijkstra's
Uses	`g(n)` only — actual cost from start
Complete?	Yes
Optimal?	Yes — for non-negative edge weights
Time	O((V + E) log V) with a binary heap
Heuristic	None — explores all directions equally

The tradeoff vs A*

Because Dijkstra has no heuristic, it expands outward in all directions like a ripple. This guarantees finding the shortest path to every node, but wastes time exploring nodes far from the goal when you only need one specific target.

Real-world use: Network routing protocols (like OSPF) use Dijkstra's to find shortest paths across all routers. GPS systems prefer A* for single-destination navigation since it's faster.

Code Runner Challenge

Dijkstra's Algorithm

View IPYNB Source

// CODE_RUNNER: Dijkstra's Algorithm

import java.util.*;

public class Main {

    static class Edge {
        String to;
        int cost;
        Edge(String to, int cost) { this.to = to; this.cost = cost; }
    }

    public static void main(String[] args) {
        // Graph:  A --5-- B
        //         |       |
        //         1       2
        //         |       |
        //         C --2-- D
        Map<String, List<Edge>> graph = new HashMap<>();
        graph.put("A", Arrays.asList(new Edge("B", 5), new Edge("C", 1)));
        graph.put("B", Arrays.asList(new Edge("A", 5), new Edge("D", 2)));
        graph.put("C", Arrays.asList(new Edge("A", 1), new Edge("D", 2)));
        graph.put("D", Arrays.asList(new Edge("B", 2), new Edge("C", 2)));

        String start = "A";

        Map<String, Integer> dist = new HashMap<>();
        Map<String, String> prev = new HashMap<>();
        for (String node : graph.keySet()) dist.put(node, Integer.MAX_VALUE);
        dist.put(start, 0);

        PriorityQueue<String> pq = new PriorityQueue<>(Comparator.comparingInt(dist::get));
        pq.add(start);
        Set<String> settled = new HashSet<>();

        System.out.println("=== Dijkstra's Algorithm ===");
        while (!pq.isEmpty()) {
            String u = pq.poll();
            if (settled.contains(u)) continue;
            settled.add(u);
            System.out.println("Settle " + u + " (dist=" + dist.get(u) + ")");

            for (Edge e : graph.get(u)) {
                int alt = dist.get(u) + e.cost;
                if (alt < dist.get(e.to)) {
                    dist.put(e.to, alt);
                    prev.put(e.to, u);
                    pq.add(e.to);
                    System.out.println("  Update " + e.to + ": dist=" + alt + " via " + u);
                }
            }
        }

        System.out.println("\n=== Shortest Distances from " + start + " ===");
        for (String node : new TreeSet<>(dist.keySet())) {
            List<String> path = new ArrayList<>();
            String p = node;
            while (p != null) { path.add(p); p = prev.get(p); }
            Collections.reverse(path);
            System.out.println(node + ": dist=" + dist.get(node) + "  path=" + String.join("->", path));
        }
    }
}
Main.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Knowledge Check: Dijkstra's Algorithm

Q1. Dijkstra's always expands the node with the smallest...

a) h(n) — heuristic estimate to goal b) g(n) — actual cost from start c) f(n) = g(n) + h(n) d) Number of neighbors

Q2. Why is Dijkstra's slower than A* for single-target pathfinding?

a) It uses a worse data structure b) It explores all directions equally with no heuristic to guide it toward the goal c) It does not use a priority queue d) It cannot handle weighted graphs

✅ A* Algorithm unlocked! Click it in the sidebar to continue.

A* Algorithm

A* (pronounced "A-star") is the best of both worlds — it combines Dijkstra's guaranteed shortest path with Greedy's heuristic guidance. It is the most widely used pathfinding algorithm in practice.

Core formula

f(n) = g(n) + h(n)
• g(n) — actual cost from start to node n (like Dijkstra)
• h(n) — estimated cost from n to goal (like Greedy)
• f(n) — total estimated cost of the cheapest path through n

Algorithm steps

Set g(start) = 0, f(start) = h(start)
Add start to a min-priority queue sorted by f(n)
Pop the node with the smallest f(n)
If it is the goal — reconstruct and return the path
For each neighbor: compute tentative_g = g(current) + edge_cost
If tentative_g < g(neighbor), update g, f, parent — re-add to queue
Repeat from step 3

Key properties

Property	A*
Uses	`f(n) = g(n) + h(n)`
Complete?	Yes
Optimal?	Yes — if `h(n)` is admissible
Time	O(b^d) — much better than Dijkstra for single target
Heuristic	Yes — steers search toward the goal

Admissibility — the key constraint

A heuristic is admissible if it never overestimates the true cost to reach the goal. If it overestimates, A* may skip the optimal path.

Manhattan distance — grid maps without diagonal moves: |dx| + |dy|
Euclidean distance — straight-line distance in open space

Connection to the Maze Runner: The maze on the right uses A* with Manhattan distance as h(n). Watch it find the shortest path — it expands far fewer nodes than Dijkstra would because the heuristic keeps it focused on the exit.

Code Runner Challenge

A* Algorithm

View IPYNB Source

// CODE_RUNNER: A* Algorithm

import java.util.*;

public class Main {

    static class Node implements Comparable<Node> {
        String name;
        double gScore;
        double fScore;
        Node parent;

        public Node(String name) {
            this.name = name;
            this.gScore = Double.MAX_VALUE;
            this.fScore = Double.MAX_VALUE;
            this.parent = null;
        }

        public int compareTo(Node other) {
            return Double.compare(this.fScore, other.fScore);
        }

        public int hashCode() { return name.hashCode(); }
        public boolean equals(Object obj) {
            if (obj instanceof Node) return name.equals(((Node) obj).name);
            return false;
        }
    }

    static class Edge {
        String to;
        double cost;
        Edge(String to, double cost) { this.to = to; this.cost = cost; }
    }

    public static List<String> findPath(Map<String, List<Edge>> graph,
                                        Map<String, Double> heuristic,
                                        String start, String goal) {
        PriorityQueue<Node> openSet = new PriorityQueue<>();
        Set<String> closedSet = new HashSet<>();
        Map<String, Node> allNodes = new HashMap<>();
        int nodesExplored = 0;

        Node startNode = new Node(start);
        startNode.gScore = 0;
        startNode.fScore = heuristic.getOrDefault(start, 0.0);
        openSet.add(startNode);
        allNodes.put(start, startNode);

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();
            nodesExplored++;

            System.out.println("Exploring: " + current.name +
                " (g=" + (int)current.gScore + ", h=" + heuristic.getOrDefault(current.name, 0.0).intValue() +
                ", f=" + (int)current.fScore + ")");

            if (current.name.equals(goal)) {
                System.out.println("\nGoal reached! Nodes explored: " + nodesExplored);
                List<String> path = new ArrayList<>();
                Node c = current;
                while (c != null) { path.add(c.name); c = c.parent; }
                Collections.reverse(path);
                return path;
            }

            closedSet.add(current.name);

            for (Edge edge : graph.getOrDefault(current.name, new ArrayList<>())) {
                if (closedSet.contains(edge.to)) continue;
                Node neighbor = allNodes.getOrDefault(edge.to, new Node(edge.to));
                if (!allNodes.containsKey(edge.to)) allNodes.put(edge.to, neighbor);

                double tentativeG = current.gScore + edge.cost;
                if (tentativeG < neighbor.gScore) {
                    neighbor.parent = current;
                    neighbor.gScore = tentativeG;
                    neighbor.fScore = tentativeG + heuristic.getOrDefault(edge.to, 0.0);
                    if (!openSet.contains(neighbor)) openSet.add(neighbor);
                }
            }
        }
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        Map<String, List<Edge>> graph = new HashMap<>();
        graph.put("A", Arrays.asList(new Edge("B", 4), new Edge("C", 2)));
        graph.put("B", Arrays.asList(new Edge("D", 3)));
        graph.put("C", Arrays.asList(new Edge("D", 6)));
        graph.put("D", new ArrayList<>());

        Map<String, Double> heuristic = new HashMap<>();
        heuristic.put("A", 5.0);
        heuristic.put("B", 2.0);
        heuristic.put("C", 4.0);
        heuristic.put("D", 0.0);

        System.out.println("=== A* Algorithm ===");
        System.out.println("f(n) = g(n) + h(n)\n");
        List<String> path = findPath(graph, heuristic, "A", "D");
        System.out.println("\nOptimal path: " + String.join(" -> ", path));
        System.out.println("Total cost: 7  (A->B: 4, B->D: 3)");
        System.out.println("\nNote: A* skipped A->C->D (cost=8) guided by the heuristic.");
    }
}
Main.main(null);

Lines: 1 Characters: 0

Output

Click "Run" in code control panel to see output ...

Knowledge Check: A* Algorithm

Q1. A* uses f(n) = g(n) + h(n). What does g(n) represent?

a) Estimated cost from n to goal b) Actual cost from start to n c) Total number of neighbors of n d) The heuristic weight

Q2. Which condition must h(n) satisfy for A* to guarantee an optimal path?

a) h(n) must always equal the true cost b) h(n) must be consistent (monotone) c) h(n) must be admissible — never overestimate the true cost d) h(n) must always be zero

🎉 You have completed all three algorithms! Try the Maze Runner on the right.

Submit Assignment

Need to update a submission later? Open the submissions dashboard.

Create Microblog Post

Reply to Post

Computer Science A

Graph Heuristics

Graph Heuristics

Algorithm Journey

Greedy Best-First Search

Core idea

Algorithm steps

Key properties

Why it can fail

Code Runner Challenge

Knowledge Check: Greedy BFS

Dijkstra's Algorithm

Core idea

Algorithm steps

Key properties

The tradeoff vs A*

Code Runner Challenge

Knowledge Check: Dijkstra's Algorithm

A* Algorithm

Core formula

Algorithm steps

Key properties

Admissibility — the key constraint

Code Runner Challenge

Knowledge Check: A* Algorithm

Submit Assignment

Course Timeline