Year 12 Graph Theory: Shortest path basics

Shortest-path questions ask which route between two vertices has the smallest total length. In an unweighted graph that may mean the fewest edges, but in a weighted graph it means the smallest sum of edge weights. The basic skill is to compare routes systematically rather than trusting the picture. Crowded networks often make one path look shortest when another route has the smaller total weight. A methodical comparison is therefore much safer than visual intuition.

A shortest path is determined by total length, not by how direct the drawing appears.

Subtopic 1: Listing candidate routes

The first step in many shortest-path questions is to list reasonable candidate routes. This does not mean writing every possible route in a huge graph, but it does mean identifying the main plausible alternatives and comparing them carefully. When the graph is small, an explicit table is often the cleanest method.

Worked example 1

Problem: In a weighted graph, the routes from

A

D

have weights:

A - B - D = 4 + 5

A - C - D = 3 + 7

, and

A - E - D = 6 + 2

. Find the shortest path.

Calculate each total: $A - B - D = 9$ .
$A - C - D = 10$ .
$A - E - D = 8$ .
Compare the totals. The smallest is $8$ .

Answer: the shortest path is

A - E - D

with total weight

8

Subtopic 2: Fewest edges versus least weight

Students often confuse the path with the fewest edges and the path with the least total weight. In an unweighted graph these ideas can coincide, but in a weighted graph they can differ significantly. A three-edge route can easily beat a two-edge route if the individual weights are much smaller. This is one of the most important conceptual distinctions in Year 12 graph theory.

Worked example 2

Problem: One route from

P

Q

uses two edges with weights

9

and

8

. Another route uses three edges with weights

4

3

, and

4

. Which is shorter?

The two-edge route has total weight $17$ .
The three-edge route has total weight $11$ .
Although it uses more edges, it is still shorter in weighted length.

Answer: the three-edge route is shorter because its total weight is

11

Why shortest-path work should be systematic

Shortest-path errors usually come from either omission or assumption. Omission means you failed to compare a relevant route. Assumption means you trusted the look of the diagram instead of the weights. A short table of candidate routes avoids both problems. Even if the question is not asking for a formal algorithm, it is still asking for organised reasoning. In graph theory, neat route comparison is often the difference between a convincing answer and an accidental guess.

Worked example 3

Problem: Explain why a visually direct route in a road network might fail to be the shortest path.

The diagram only shows layout, not necessarily total cost.
Edge weights may represent time, distance, or expense.
A route that looks direct may contain heavier edges than a slightly less direct alternative.

Answer: the shortest path depends on total weight, not on appearance alone.

Common traps

Choosing the path that looks shortest without adding the weights.
Comparing edge counts when the graph is weighted.
Leaving out a candidate route that turns out to be better.
Adding the wrong edge weights because the diagram is crowded.

Revision focus

For revision, practise turning each shortest-path question into a compact table: route, calculation, total. This keeps the comparison transparent and makes it easier to spot omitted candidates. It also trains you to separate route identification from arithmetic, which reduces mistakes.

It is also worth stating the final answer in full, such as "the shortest path from $A$ to $D$ is $A - E - D$ with total weight $8$ ." That final sentence confirms both the route and its length and makes the reasoning easier to audit.

Practice links

Shortest path