A-level Computer Science revision · Data structures and algorithms

Dijkstra's algorithm and A*

The idea

Dijkstra's algorithm finds the shortest path from a start node to all others in a weighted graph with non-negative weights. It repeatedly visits the unvisited node with the smallest known distance and updates its neighbours. A* adds a heuristic estimate of the distance to the goal, so it explores fewer nodes towards a single target.

  1. Set start distance 0, others infinity.
  2. Visit the closest unvisited node; update neighbours if shorter.
  3. A*: f = g (cost so far) + h (heuristic).

Watch out A* is only guaranteed to find the shortest path if the heuristic never overestimates.

See it worked

Worked example

A→B is 4, A→C is 1, C→B is 2. What is the shortest distance from A to B?

  1. Direct A→B: 4.
  2. Via C: 1 + 2 = 3.
  3. Shortest is 3.

Answer 3

Your turn

Question 12 marks

A→B 7, A→C 3, C→D 2, D→B 1, C→B 5. What is the shortest distance from A to B?

Question 21 mark

How does A* differ from Dijkstra's algorithm?

Choose one
Question 31 mark

Dijkstra's algorithm does not work correctly with:

Choose one

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms