Year 12 Graph Theory: Weighted shortest-path problems

Once shortest-path basics are understood, the next step is handling busier weighted networks where a simple visual check is no longer enough. These problems require more disciplined elimination of poor routes and clearer tracking of running totals. The key is not memorising a sophisticated algorithm for every question. It is learning how to organise route comparison so that you can prove one path is better than the alternatives instead of merely suspecting it.

In a larger weighted network, keep a running comparison of current best totals so weak routes can be discarded early.

Subtopic 1: Comparing multiple branches efficiently

In a larger network, several routes may share part of their journey before branching. Rather than recalculating everything from scratch, you should preserve partial totals and extend them. This makes the comparison more efficient and reduces arithmetic repetition. Even without naming a formal shortest- path algorithm, this is the same kind of logic: build the route totals systematically and keep track of the best available option to each intermediate point.

Worked example 1

Problem: From

A

F

, compare the routes

A - B - F

with weights

3 + 9

A - C - E - F

with weights

2 + 4 + 3

, and

A - D - E - F

with weights

5 + 1 + 3

Compute the totals: $A - B - F = 12$ .
$A - C - E - F = 9$ .
$A - D - E - F = 9$ .
Two routes tie for best total weight.

Answer: the shortest-path weight is

9

, achieved by both

A - C - E - F

and

A - D - E - F

Subtopic 2: Rejecting poor routes early

Suppose you already know a route of total weight $10$ . If another candidate route has already reached weight $12$ before even arriving at the destination, that route can be rejected immediately. This kind of pruning is extremely useful in examination settings because it keeps the comparison manageable and prevents wasted time on clearly inferior options.

Worked example 2

Problem: You already found a route from

P

T

of total weight

14

. Another candidate route has partial weight

16

before its final edge, and every edge weight is positive. Can it still be the shortest path?

The route already exceeds the current best total before it has even finished.
Since the final edge must add a positive amount, the completed total will be greater than $16$ .
That cannot beat the known total of $14$ .

Answer: no, it can be rejected immediately.

What weighted reasoning adds

Weighted networks are a good reminder that route problems are really optimisation problems. You are not simply finding any valid path. You are minimising total cost under the structure of the graph. This optimisation viewpoint is helpful because it tells you what counts as evidence: not that a route exists, but that no cheaper route remains untested. Organised comparison is therefore part of the mathematics, not just good handwriting.

Worked example 3

Problem: Explain why two different paths can both be shortest paths in the same network.

Shortest means minimum total weight.
If two different routes have the same minimum total, neither is better than the other.
So the graph can have more than one shortest path between the same vertices.

Answer: multiple shortest paths can exist when different routes share the same minimum total weight.

Connecting this to real networks

In real transport or communication problems, weights may represent time, cost, distance, or risk. That means the "best" route depends entirely on what the weights mean. A route with fewer roads may be worse if the travel times are slower. A route that is geographically longer may still be cheaper. Graph theory becomes especially powerful when you keep that interpretation visible and remember that the weights are the criterion being optimised.

Common traps

Continuing to evaluate clearly inferior routes after a smaller total is already known.
Assuming the path with fewer edges must be better in a weighted network.
Failing to recognise a tie between two best routes.
Reporting the total weight without stating the actual path.

Revision focus

In revision, practise annotating the graph with partial totals as you extend routes. This makes the comparison dynamic rather than repetitive and helps you see when a branch should be abandoned. It also prepares you for denser network problems where a simple list of complete routes would be inefficient.

Another useful habit is to finish with a brief justification such as "all other candidate routes exceed total weight 9." That sentence shows why the chosen route is genuinely shortest rather than merely one convenient answer among many.

Practice links

Shortest path