A sat nav, a game character and a delivery robot all face the same problem: a map of places joined by routes, and a need to find the cheapest way through it. AI represents that map as a graph and searches it with Dijkstra's algorithm or with A*, which uses a heuristic to head straight for the goal.
A graph is a set of nodes (vertices) joined by edges (arcs). Edges can carry weights (a cost such as distance or time) and can be directed or undirected. AI uses graphs to model states and the moves between them, then searches them. Dijkstra's algorithm always visits the unvisited node with the smallest distance from the start, so it finds the shortest path to every node. A* chooses the node with the smallest f = g + h, where g is the cost so far and h is a heuristic estimate of the cost still to go, so it usually reaches the goal after visiting far fewer nodes.
Fig. 1: a weighted graph; the highlighted route A-C-B-D-E-F is the shortest path from A to F (13 km)
Section 01
Why AI uses graphs.
Many AI problems are really questions about connections: which places are linked, which game positions can follow each other, which actions lead to the goal. A graph captures exactly that and nothing else, which is a good example of abstraction.
Node (vertex): one place or state, such as a junction on a road map, a room in a game level or a board position.
Edge (arc): a connection between two nodes, such as a road or a legal move. Nodes joined by an edge are adjacent (neighbours).
Weighted graph: each edge has a value (cost), such as distance, time, fuel or risk. An unweighted graph only records whether a connection exists.
Directed graph: edges have a direction (a one-way street); in an undirected graph every edge can be travelled both ways.
How graphs aid AI: route planning (sat nav, delivery robots), path finding for characters in games, network routing, and representing problem states so a search algorithm can find a sequence of moves from the start state to a goal state.
Examiner trap
The syllabus does not ask you to write code for a graph or a search. It asks you to explain how graphs help AI and to trace Dijkstra and A* by hand, so practise clear, complete working tables.
Section 02
Dijkstra's algorithm.
Dijkstra's algorithm finds the shortest distance from a start node to every other node in a graph whose weights are not negative. Each node keeps a working (tentative) distance, which can only get smaller.
1. Set up: the start node gets distance 0; every other node gets ∞. All nodes are unvisited.
2. Choose: visit the unvisited node with the smallest distance. Its distance is now final.
3. Update: for each unvisited neighbour, work out (distance of current node + edge weight). If that is smaller than the neighbour's current distance, replace it and record the current node as its previous node.
4. Repeat steps 2 and 3 until every node is visited (or the goal is visited). Read the path backwards from the goal using the previous nodes.
Visit
A
B
C
D
E
F
start
0
∞
∞
∞
∞
∞
A (0)
0
4 (A)
2 (A)
∞
∞
∞
C (2)
3 (C)
2
10 (C)
12 (C)
∞
B (3)
3
8 (B)
12 (C)
∞
D (8)
8
10 (D)
14 (D)
E (10)
10
13 (E)
F (13)
13
Worked example Trace on Fig. 1
Use Dijkstra's algorithm on the graph in Fig. 1 to find the shortest distance and route from A to F.
Start: A = 0, all others ∞. Visit A: B becomes 0 + 4 = 4 and C becomes 0 + 2 = 2.
Smallest unvisited is C (2). Via C: B = 2 + 1 = 3 (better than 4, so B's previous node becomes C), D = 2 + 8 = 10, E = 2 + 10 = 12.
Smallest unvisited is B (3). Via B: D = 3 + 5 = 8 (better than 10).
Visit D (8). Via D: E = 8 + 2 = 10 (better than 12), F = 8 + 6 = 14.
Visit E (10). Via E: F = 10 + 3 = 13 (better than 14). Finally visit F (13).
Visit order A, C, B, D, E, F. Follow previous nodes back from F: F ← E ← D ← B ← C ← A.
Answer: Shortest distance 13 km, route A → C → B → D → E → F
Your turn
Using the table above, give the shortest distance from A to D and the route.
8 km, route A → C → B → D (A → B → D is 9 and A → C → D is 10)
Examiner trap
The edge A to B is the most direct way to B, but it is not the shortest: 4 is beaten by A → C → B = 3. Always compare and update; never treat a distance as final until you visit that node.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
In Dijkstra's algorithm, which node is visited next?
Quick check+10 XP
Using Fig. 1, what is the shortest distance from A to D?
Quick check+10 XP
In the A* algorithm, what does h(n) represent?
Quick check+10 XP
What makes a heuristic admissible?
Section 03
A* and the heuristic.
Dijkstra spreads out evenly in every direction, so it wastes time on nodes that lead away from the goal. A* adds a heuristic, h, an estimate of the distance still to go (for example, the straight-line distance to the goal), so the search is pulled towards the goal.
g(n): the actual cost of the best path found so far from the start to node n (exactly Dijkstra's distance).
h(n): the heuristic: an estimate of the cost from n to the goal, given for each node (h of the goal is 0).
f(n) = g(n) + h(n): the estimated total cost of a route through n. A* always expands the open node with the smallest f.
Stop when the goal node is chosen for expansion. If h never overestimates the true remaining cost (it is admissible), the path found is guaranteed to be the shortest.
A: 12 (7 + 5 is worse than 4); E: 12; D: 12; G: 11 + 0 = 11
G (11 + 0 = 11)
goal reached: path S → B → C → G, cost 11
Worked example A* against Dijkstra
On the graph above, how many nodes does each algorithm visit before it settles the route from S to G?
A* expands S, then B (f = 10), then C (f = 11), then G (f = 11): 4 nodes. A, D and E are never expanded because their f values (12) are bigger.
Dijkstra uses only g, so from S it visits E (2), B (3), A (4), C (7), D (9) and only then G (11): 7 nodes.
Both find the same route, S → B → C → G with cost 11, because this heuristic never overestimates.
Answer: A* visits 4 nodes; Dijkstra visits all 7
Your turn
After S is expanded, Dijkstra would visit E next. Why does A* choose B instead?
E has the smallest g (2), but its f = 2 + 10 = 12: it leads away from G. B has f = 3 + 7 = 10, the smallest f, so A* expands B.
Examiner trap
Do not stop A* when the goal first appears in the open list. Stop when the goal is chosen (has the smallest f): a cheaper route to it may still be found before then.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
Dijkstra's algorithm is applied to Fig. 1 starting at A. In what order are the nodes visited?
Exam style+20 XP
On the A* graph, S and then B have been expanded. Which node is expanded next?
Exam style+20 XP
Why does A* usually visit fewer nodes than Dijkstra's algorithm?
Exam style+20 XP
An AI route planner models a city as a graph. What would an edge weight most sensibly represent?
Skill unlocked
Graphs, Dijkstra and A*, mastered.
This skill is now recorded on your profile. Keep the chain going.