18.1 Artificial Intelligence (AI)

Bulk view disabled for Guests. View lessons individually.

Graphs, A* and Dijkstra's Algorithm

Scope note. You are required to understand the purpose and structure of a graph, and to use A* and Dijkstra's algorithms to perform searches. You are not required to write algorithms to set up, access, or search graphs — so the emphasis is on tracing and explaining, not coding.

1. What Is a Graph?

A graph is an abstract data type consisting of nodes (also called vertices) connected by edges (also called arcs). Unlike a tree, a graph has no root and may contain cycles, and any node may connect to any other.

TermMeaning
Node / vertexAn item of data in the graph
Edge / arcA connection between two nodes
WeightA value attached to an edge, e.g. distance, time or cost
Directed graphEdges may be travelled in one direction only
Undirected graphEdges may be travelled in either direction
Adjacency matrixA 2D array storing the weight between every pair of nodes
Adjacency listEach node stores a list of only the nodes it connects to
Matrix or list? An adjacency matrix gives instant lookup of any edge but wastes space when few edges exist (a sparse graph). An adjacency list uses space proportional to the number of actual edges, but finding whether two specific nodes connect takes longer. Choose the matrix for dense graphs, the list for sparse ones.

Why graphs matter for AI

Many problems become searches over a graph: route-finding in a satellite navigation system, moving a character through a game map, planning moves in a puzzle, or modelling a network. AI needs to find a good path through such a graph efficiently, and that is what these two algorithms do.

2. The Example Graph

Both algorithms below are traced on this weighted, undirected graph. We are travelling from A to E.

4 3 A --------- B --------- E | | | 2 | 1 | | 6 | | | C --------- D ----------+ 5 7 Edges: A-B = 4 A-C = 2 B-D = 1 B-E = 3 C-D = 5 D-E = 7

3. Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a start node to every other node, using only the actual weights of the edges travelled so far.

The method

  1. Set the distance to the start node to 0, and every other node to infinity.
  2. Mark all nodes unvisited.
  3. Select the unvisited node with the smallest distance — call it the current node.
  4. For each neighbour, calculate distance to current + edge weight. If this is less than the neighbour's recorded distance, update it and record the current node as its predecessor.
  5. Mark the current node visited.
  6. Repeat from step 3 until the destination is visited or no unvisited nodes remain.

Traced on the example

StepCurrentABCDEVisited
Init–0∞∞∞∞–
1A042∞∞A
2C (2)0427∞A, C
3B (4)04257A, C, B
4D (5)04257A, C, B, D
5E (7)04257all

At step 3, D's distance improved from 7 (via C) to 5 (via B), because 4 + 1 = 5 beats 2 + 5 = 7. That replacement is the heart of the algorithm.

Result: the shortest distance from A to E is 7, via the path A → B → E. The path is recovered by following predecessors backwards from E.

4. A* Algorithm

A* improves on Dijkstra by adding an estimate of the distance still remaining. It therefore heads towards the goal instead of expanding evenly in all directions.

f(n) = g(n) + h(n) g(n) = actual cost from the start node to n h(n) = heuristic - the estimated cost from n to the goal f(n) = estimated total cost of a route through n

A* always expands the unvisited node with the lowest f value.

The heuristic

The heuristic is an informed guess about the remaining distance — for map routing, typically the straight-line distance to the destination. For A* to be guaranteed to find the shortest path, the heuristic must never overestimate the true remaining cost. Such a heuristic is called admissible.

Traced on the example

Using these straight-line estimates to E: h(A)=6, h(B)=3, h(C)=6, h(D)=5, h(E)=0

Nodeg (actual from A)h (estimate to E)f = g + h
A066
C268
B437
D5510
E707

From A, both B (f=7) and C (f=8) are options. A* expands B first because its f value is lower — and B leads straight to E with a total of 7. Dijkstra, by contrast, expanded C first because C's actual distance (2) was smallest. A* reached the goal having examined fewer nodes.

5. Comparing the Two

Dijkstra's algorithmA*
UsesActual cost only, g(n)Actual cost plus heuristic, g(n) + h(n)
Search shapeExpands outwards in all directionsDirected towards the goal
Nodes examinedMoreFewer, if the heuristic is good
FindsShortest path to every nodeShortest path to one goal
Guarantees shortest path?AlwaysOnly if the heuristic never overestimates
The relationship worth remembering: if the heuristic is always zero, then f(n) = g(n) and A* behaves exactly like Dijkstra's algorithm. Dijkstra is the special case of A* with no heuristic.

6. Exam Focus

Show the table, not just the answer. Trace questions award marks for the intermediate distances and for updating a node when a shorter route is found. Give the running table and the final path.
State the path as well as the distance. "The shortest distance is 7" is only half the answer; the route A → B → E is usually worth a separate mark.
Define the heuristic precisely. h(n) is the estimated cost from n to the goal. Describing it as the distance travelled so far confuses it with g(n) and scores nothing.
Explain A*'s advantage in the right terms. A* is not faster because it "knows the answer"; it is faster because it examines fewer nodes, being guided towards the goal by the heuristic.

Quick self-check

  • Define node, edge and weight.
  • Give one advantage of an adjacency list over an adjacency matrix.
  • State the A* formula and define each term.
  • Why must a heuristic never overestimate the remaining distance?
  • Under what condition does A* behave identically to Dijkstra's algorithm?
  • Trace Dijkstra from C to E on the example graph.