Shortest/longest paths | Year 11

01 / LEARN

Understand the idea.

Minimise the sum, not the edge count

A shortest route minimises the sum of weights, not the number of edges. In a small acyclic network, list all directed paths and compare totals. For larger non-negative networks, Dijkstra’s method systematically settles the smallest currently reachable distance.

When using labels, start the source at zero and other vertices at infinity. Settle the smallest temporary label, update outgoing neighbours, and record predecessors so the route can be reconstructed. Equal totals may produce multiple shortest routes.

A longest walk may not exist

In a directed acyclic network, a longest path can be found by comparing all available path totals or by processing vertices in arrow order while retaining the largest accumulated total. Acyclicity prevents unlimited repetitions.

A longest walk need not have a finite maximum if a reachable positive cycle can be repeated before reaching the destination. Each extra circuit adds weight. State whether repeats are allowed and whether the cycle lies on an accessible source-to-destination journey.

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

Find the shortest

Find a shortest A-to-E route in the displayed directed network.

Worked solution

1
List every directed A-to-E path.
From A, the B branch must continue through D; the C branch either goes directly to E or continues through D. These give exactly three paths.
2
Calculate their weights.
$\begin{aligned} w (A \to C \to E) & = 5 + 6 = 11 \\ w (A \to C \to D \to E) & = 5 + 2 + 7 = 14 \\ w (A \to B \to D \to E) & = 3 + 6 + 7 = 16 \end{aligned}$
Each total adds the edge weights in its permitted direction.
3
Select the smallest total.
$min (11, 14, 16) = 11$
A to C to E has the least weight among all three possible paths.

Answer

A→C→E, weight 11.

EXAMPLE 02

Find the longest

Find a longest A-to-E path in the same acyclic network.

Worked solution

1
Enumerate the available paths.
The same acyclic graph permits A to C to E, A to C to D to E, and A to B to D to E; there is no further branching route.
2
Calculate and compare their totals.
$\begin{aligned} w (A \to C \to E) & = 11 \\ w (A \to C \to D \to E) & = 14 \\ w (A \to B \to D \to E) & = 16 \end{aligned}$
All possible path weights are included, so selecting the largest is conclusive.
3
State the longest path.
$max (11, 14, 16) = 16$
A to B to D to E achieves weight sixteen, and no omitted path remains to exceed it.

Answer

A→B→D→E, weight 16.

03 / YOUR TURN

Try it yourself.

Check your understanding

Why is there no finite longest walk around a positive cycle if repeated circuits are allowed?

Show answer & reasoning

Every additional circuit adds weight.

If a positive cycle has total weight $c > 0$ , repeating it $k$ times adds $k c$ . With no upper bound on repetitions, the walk weight has no finite maximum.

Keep practising

6 worksheet questions · 12 marks

Open worksheet Worked solutions

Read the questions online

P→Q→S weighs $4 + 8$ and P→R→S weighs $7 + 2$ . Which is shorter?
2 marks
Edges are A→B (8), A→C (3), C→B (2), B→D (4), C→D (9). Find the shortest A-to-D path.
2 marks
In that same acyclic network, find a longest A-to-D path.
2 marks
A route takes 18 min; a direct one-edge route takes 20 min. Which is faster?
2 marks
Can a route using a closed road be the shortest feasible route?
2 marks
A→B has weight 2 and B→A weight 3. Is there a longest A-to-A walk when repetition is allowed?
2 marks

Read the worked solutions

Equivalent correct methods earn the corresponding marks. Include units where asked.

P→Q→S weighs $4 + 8$ and P→R→S weighs $7 + 2$ . Which is shorter?
2 marks
The alternatives total 12 and 9.
Choose 9.
P→R→S, weight 9.
Edges are A→B (8), A→C (3), C→B (2), B→D (4), C→D (9). Find the shortest A-to-D path.
2 marks
The paths total 12, 9 and 12.
The via-C-and-B path is smallest.
A→C→B→D, weight 9.
In that same acyclic network, find a longest A-to-D path.
2 marks
The three path totals are 12, 9 and 12.
Two paths tie for the maximum.
A→B→D or A→C→D, each weight 12.
A route takes 18 min; a direct one-edge route takes 20 min. Which is faster?
2 marks
Compare times rather than edge counts.
It saves 2 min.
The 18-minute route.
Can a route using a closed road be the shortest feasible route?
2 marks
Remove the closed edge from the model.
Recalculate with the permitted edges.
No.
A→B has weight 2 and B→A weight 3. Is there a longest A-to-A walk when repetition is allowed?
2 marks
One circuit totals 5.
Repeating it $n$ times gives $5 n$ , with no upper bound.
No finite maximum.

Checking saved progress…

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 1 General Mathematics: matrices and networks. Original learning resources follow the approved Ascent Library chapter map.

Official curriculum source ↗

In this lesson

Understand the idea.

Minimise the sum, not the edge count

A longest walk may not exist

See the method in action.

Find the shortest

List every directed A-to-E path.

Calculate their weights.

Select the smallest total.

Find the longest

Enumerate the available paths.

Calculate and compare their totals.

State the longest path.

Try it yourself.

Check your understanding

Keep practising