Free A-Level Computer Science guide

Dijkstra and A*: find a shortest path without guessing

Trace tentative distances on a weighted graph, record the predecessor that gives each best route, and see how A* uses a goal estimate to choose the next node.

Content owner: Michael Print · Written for A-Level learners · Checked against official specifications

How do Dijkstra and A* choose the next node?

Dijkstra selects the unprocessed node with the lowest tentative cost from the start, g. It improves neighbours' costs by testing whether the route through that node is cheaper.

A* selects by f = g + h: the cost found so far plus a heuristic estimate of the remaining cost to the goal. An appropriate heuristic can guide the search, but its conditions matter for shortest-path guarantees.

Keep the three A* scores separate

g: cost so far: Add the edge weights along the best route found from the start to this node.
h: remaining estimate: Estimate the cost from this node to the goal. Use the same units as g.
f = g + h: priority: Compare waiting nodes using this score. It is an estimate, rather than the known final route cost.

Before you start

You should be able to read a table, follow a loop and add edge costs. A graph contains vertices (nodes) and edges (connections). A directed edge is one-way; an undirected edge works both ways. These methods require non-negative edge weights in our examples.

Update tentative costs and predecessors when a better route is found.
Reconstruct a path and distinguish its cost from a priority score.
Explain why an overestimating heuristic can mislead A*.

Read the graph and state the objective

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

A shortest path minimises the sum of weights. It need not have the fewest edges.

Compare three routes on this graph
Route	Add the edge costs	Total
S → A → G	4 + 3	7
S → B → G	1 + 7	8
S → B → A → G	1 + 2 + 3	6

Worked example

Dijkstra: improve the whole route cost

Initialise: S has cost 0. Every other cost is infinity, meaning no route is known.
Select S: discover A at 4 and B at 1.
Select B: improve A to 1 + 2 = 3. Discover G at 1 + 7 = 8.
Select A: improve G to 3 + 3 = 6.
Select G: stop at cost 6 for this single-goal task. Non-negative edge costs let us finalise a selected minimum.

Dijkstra costs after expanding each selected node
Selected	A	B	G	Changed predecessor
Initial	∞	∞	∞	None
S	4	1	∞	A ← S; B ← S
B	3	1	8	A ← B; G ← B
A	3	1	6	G ← A
G (goal)	3	1	6	Stop

Follow predecessors backwards: G ← A ← B ← S. Reverse that sequence to get the route S → B → A → G. Stop when the goal is selected at its minimum cost; first discovering G at 8 does not prove it is optimal.

A*: add an estimate to the cost so far

Use fixed heuristic values h(S) = 5, h(A) = 3, h(B) = 4 and h(G) = 0. Each is no greater than that node's actual remaining shortest cost (6, 3, 5 and 0 respectively), so the heuristic is admissible.

A* frontier scores during the same search
After expanding	Candidates shown as g + h = f	Next selected
S	A: 4 + 3 = 7; B: 1 + 4 = 5	B
B	A: 3 + 3 = 6; G: 8 + 0 = 8	A
A	G: 6 + 0 = 6	G

This small example selects nodes in the same order as Dijkstra. A* is not guaranteed to inspect fewer nodes on every problem. Setting all h values to zero gives Dijkstra's priority rule.

Match the heuristic to the implementation

If graph search permanently closes nodes, a consistent heuristic is a standard sufficient condition. For every directed edge u → v, require h(u) ≤ weight(u,v) + h(v). These estimates satisfy it in both directions.

The Python example can queue an improved node again. With non-negative weights, admissible estimates and h(goal) = 0, stopping when the goal is selected yields an optimal route.

Original A-Level practice

Four original questions total 15 marks. Each question includes its graph and the rules it needs; marking guidance is indicative.

Question 1

4 marks

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

Dijkstra rules: start with g(S) = 0 and every other cost at infinity. Expand the unprocessed node with the lowest tentative cost. Update a neighbour if g(current) + edge cost improves its known cost.

Run Dijkstra from S until B has been expanded. State the tentative costs for A and G and show each calculation.

Show solution and marking guidance

Indicative answer: After B, A has tentative cost 3 (1), from 1 + 2 (1); G has tentative cost 8 (1), from 1 + 7 (1). Both updated predecessors are B.

Question 2

4 marks

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

Dijkstra rules: start with g(S) = 0 and every other cost at infinity. Expand the unprocessed node with the lowest tentative cost. Whenever g(current) + edge cost improves a neighbour's cost, record current as its predecessor.

Finish a Dijkstra trace from S to G, recording the predecessors. Reconstruct the final route and give its cost. Explain why we cannot stop when G is first discovered at 8.

Show solution and marking guidance

Indicative answer

Backwards predecessor chain G ← A ← B ← S (1).
Forward route S → B → A → G (1), total 1 + 2 + 3 = 6 (1).
The first discovery at cost 8 can improve before G is selected; discovery alone is not finalisation (1).

Question 3

4 marks

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

A* rules: start at S with g(S) = 0; g records route cost so far. Select the waiting node with the lowest f = g + h. Use h(S) = 5, h(A) = 3, h(B) = 4 and h(G) = 0.

Calculate the A* scores of A and B immediately after expanding S. State the next node and explain what changes when all heuristic values are zero.

Show solution and marking guidance

Indicative answer: f(A) = 4 + 3 = 7 (1); f(B) = 1 + 4 = 5 (1). Select B because it has the smaller f-score (1). Setting every h to zero removes the estimate, so selection is by g as in Dijkstra (1).

Question 4

3 marks

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

A* rules: start at S with g(S) = 0. Improve neighbours using g(current) + edge cost. Select the waiting node with the lowest f = g + h; stop when G is selected.

Baseline estimates: h(S) = 5, h(A) = 3, h(B) = 4 and h(G) = 0.

Change only h(B) from 4 to 100. Explain the route cost returned by this A* stopping rule and why it can be wrong.

Show solution and marking guidance

Indicative answer

A now has f = 7 while B has f = 101, so A is selected first (1).
A discovers G at cost 7, f = 7, and G is selected before B, returning cost 7 (1).
h(B) = 100 overestimates the actual remaining cost 5, so the optimal cost-6 route through B is missed by this stopping rule (1).

Optional: run Dijkstra and A* in Python

Run both searches on the same data

Priority queue, better-route updates and predecessor reconstructionPython

from heapq import heappop, heappush
from math import inf


def shortest_path(graph, start, goal, heuristic):
    # Preconditions: finite graph, non-negative edge weights,
    # all neighbours are keys, and a heuristic entry for every node.
    # For optimal A*: h never overestimates and h(goal) is zero.
    best = {start: 0}
    previous = {}
    waiting = [(heuristic[start], 0, start)]
    while waiting:
        priority, cost, node = heappop(waiting)
        if cost != best[node]:
            continue  # An older, more expensive entry is stale.
        if node == goal:
            route = [goal]
            while route[-1] != start:
                route.append(previous[route[-1]])
            route.reverse()
            return cost, route
        for neighbour, weight in graph[node].items():
            candidate = cost + weight
            if candidate < best.get(neighbour, inf):
                best[neighbour] = candidate
                previous[neighbour] = node
                heappush(waiting, (
                    candidate + heuristic[neighbour],
                    candidate,
                    neighbour
                ))
    return inf, []  # No route to the goal.


def dijkstra(graph, start, goal):
    return shortest_path(graph, start, goal, {v: 0 for v in graph})


graph = {
    "S": {"A": 4, "B": 1},
    "A": {"S": 4, "B": 2, "G": 3},
    "B": {"S": 1, "A": 2, "G": 7},
    "G": {"A": 3, "B": 7}
}
h = {"S": 5, "A": 3, "B": 4, "G": 0}

print(dijkstra(graph, "S", "G"))
print(shortest_path(graph, "S", "G", h))
# Both print: (6, ['S', 'B', 'A', 'G'])

The adjacency dictionaries store neighbour costs.
heappop chooses the smallest tuple: f first, then g, then node name for ties.
If a better route is found later, skip the older queued entry.
A missing route returns (inf, []). Start equal to goal returns cost 0 and the one-node route.

State the representation before comparing costs

Different graph representations and priority queues have different costs.
On a simple graph, Dijkstra with an adjacency list and binary heap usually takes O((V + E) log V) time.
This teaching version retains stale entries, so it can store O(V + E) working data.
A* has no single fixed implementation complexity: the heuristic and explored search space strongly affect its work.

Specification and algorithm references

OCR H446 §2.3.1(f) names Dijkstra and A*. Graph representations connect to §1.4.2. The graph, traces and questions here are independently written.

These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.

Found an error? Email a correction.

Need help applying this to unfamiliar questions?

Use the free examples first, then explore one-to-one tuition if guided practice would help.

Explore tuition Email Michael

Free A-Level Computer Science guide

Dijkstra and A*: find a shortest path without guessing

Trace tentative distances on a weighted graph, record the predecessor that gives each best route, and see how A* uses a goal estimate to choose the next node.

Content owner: Michael Print · Written for A-Level learners · Checked against official specifications

How do Dijkstra and A* choose the next node?

Dijkstra selects the unprocessed node with the lowest tentative cost from the start, g. It improves neighbours' costs by testing whether the route through that node is cheaper.

Keep the three A* scores separate

g: cost so far: Add the edge weights along the best route found from the start to this node.
h: remaining estimate: Estimate the cost from this node to the goal. Use the same units as g.
f = g + h: priority: Compare waiting nodes using this score. It is an estimate, rather than the known final route cost.

Before you start

Update tentative costs and predecessors when a better route is found.
Reconstruct a path and distinguish its cost from a priority score.
Explain why an overestimating heuristic can mislead A*.

Read the graph and state the objective

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

A shortest path minimises the sum of weights. It need not have the fewest edges.

Compare three routes on this graph
Route	Add the edge costs	Total
S → A → G	4 + 3	7
S → B → G	1 + 7	8
S → B → A → G	1 + 2 + 3	6

Worked example

Dijkstra: improve the whole route cost

Initialise: S has cost 0. Every other cost is infinity, meaning no route is known.
Select S: discover A at 4 and B at 1.
Select B: improve A to 1 + 2 = 3. Discover G at 1 + 7 = 8.
Select A: improve G to 3 + 3 = 6.
Select G: stop at cost 6 for this single-goal task. Non-negative edge costs let us finalise a selected minimum.

Dijkstra costs after expanding each selected node
Selected	A	B	G	Changed predecessor
Initial	∞	∞	∞	None
S	4	1	∞	A ← S; B ← S
B	3	1	8	A ← B; G ← B
A	3	1	6	G ← A
G (goal)	3	1	6	Stop

A*: add an estimate to the cost so far

A* frontier scores during the same search
After expanding	Candidates shown as g + h = f	Next selected
S	A: 4 + 3 = 7; B: 1 + 4 = 5	B
B	A: 3 + 3 = 6; G: 8 + 0 = 8	A
A	G: 6 + 0 = 6	G

This small example selects nodes in the same order as Dijkstra. A* is not guaranteed to inspect fewer nodes on every problem. Setting all h values to zero gives Dijkstra's priority rule.

Match the heuristic to the implementation

The Python example can queue an improved node again. With non-negative weights, admissible estimates and h(goal) = 0, stopping when the goal is selected yields an optimal route.

Original A-Level practice

Four original questions total 15 marks. Each question includes its graph and the rules it needs; marking guidance is indicative.

Question 1

4 marks

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

Run Dijkstra from S until B has been expanded. State the tentative costs for A and G and show each calculation.

Show solution and marking guidance

Indicative answer: After B, A has tentative cost 3 (1), from 1 + 2 (1); G has tentative cost 8 (1), from 1 + 7 (1). Both updated predecessors are B.

Question 2

4 marks

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

Finish a Dijkstra trace from S to G, recording the predecessors. Reconstruct the final route and give its cost. Explain why we cannot stop when G is first discovered at 8.

Show solution and marking guidance

Indicative answer

Backwards predecessor chain G ← A ← B ← S (1).
Forward route S → B → A → G (1), total 1 + 2 + 3 = 6 (1).
The first discovery at cost 8 can improve before G is selected; discovery alone is not finalisation (1).

Question 3

4 marks

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

A* rules: start at S with g(S) = 0; g records route cost so far. Select the waiting node with the lowest f = g + h. Use h(S) = 5, h(A) = 3, h(B) = 4 and h(G) = 0.

Calculate the A* scores of A and B immediately after expanding S. State the next node and explain what changes when all heuristic values are zero.

Show solution and marking guidance

Question 4

3 marks

Each line can be used in either direction. Its number is a cost; the aim is to minimise total cost from S to G.

A* rules: start at S with g(S) = 0. Improve neighbours using g(current) + edge cost. Select the waiting node with the lowest f = g + h; stop when G is selected.

Baseline estimates: h(S) = 5, h(A) = 3, h(B) = 4 and h(G) = 0.

Change only h(B) from 4 to 100. Explain the route cost returned by this A* stopping rule and why it can be wrong.

Show solution and marking guidance

Indicative answer

A now has f = 7 while B has f = 101, so A is selected first (1).
A discovers G at cost 7, f = 7, and G is selected before B, returning cost 7 (1).
h(B) = 100 overestimates the actual remaining cost 5, so the optimal cost-6 route through B is missed by this stopping rule (1).

Optional: run Dijkstra and A* in Python

Run both searches on the same data

Priority queue, better-route updates and predecessor reconstructionPython

from heapq import heappop, heappush
from math import inf


def shortest_path(graph, start, goal, heuristic):
    # Preconditions: finite graph, non-negative edge weights,
    # all neighbours are keys, and a heuristic entry for every node.
    # For optimal A*: h never overestimates and h(goal) is zero.
    best = {start: 0}
    previous = {}
    waiting = [(heuristic[start], 0, start)]
    while waiting:
        priority, cost, node = heappop(waiting)
        if cost != best[node]:
            continue  # An older, more expensive entry is stale.
        if node == goal:
            route = [goal]
            while route[-1] != start:
                route.append(previous[route[-1]])
            route.reverse()
            return cost, route
        for neighbour, weight in graph[node].items():
            candidate = cost + weight
            if candidate < best.get(neighbour, inf):
                best[neighbour] = candidate
                previous[neighbour] = node
                heappush(waiting, (
                    candidate + heuristic[neighbour],
                    candidate,
                    neighbour
                ))
    return inf, []  # No route to the goal.


def dijkstra(graph, start, goal):
    return shortest_path(graph, start, goal, {v: 0 for v in graph})


graph = {
    "S": {"A": 4, "B": 1},
    "A": {"S": 4, "B": 2, "G": 3},
    "B": {"S": 1, "A": 2, "G": 7},
    "G": {"A": 3, "B": 7}
}
h = {"S": 5, "A": 3, "B": 4, "G": 0}

print(dijkstra(graph, "S", "G"))
print(shortest_path(graph, "S", "G", h))
# Both print: (6, ['S', 'B', 'A', 'G'])

The adjacency dictionaries store neighbour costs.
heappop chooses the smallest tuple: f first, then g, then node name for ties.
If a better route is found later, skip the older queued entry.
A missing route returns (inf, []). Start equal to goal returns cost 0 and the one-node route.

State the representation before comparing costs

Different graph representations and priority queues have different costs.
On a simple graph, Dijkstra with an adjacency list and binary heap usually takes O((V + E) log V) time.
This teaching version retains stale entries, so it can store O(V + E) working data.
A* has no single fixed implementation complexity: the heuristic and explored search space strongly affect its work.

Specification and algorithm references

OCR H446 §2.3.1(f) names Dijkstra and A*. Graph representations connect to §1.4.2. The graph, traces and questions here are independently written.

Found an error? Email a correction.

Need help applying this to unfamiliar questions?

Use the free examples first, then explore one-to-one tuition if guided practice would help.

Explore tuition Email Michael