Shortest/longest paths | Year 11

01 / LEARN

The idea, step by step

Minimise the sum, not the edge count

A shortest path minimises the total of its edge weights. For non-negative weights, start at the source with label zero and repeatedly make the smallest temporary label permanent. Update neighbours by testing a journey through the newly permanent vertex.

Record a predecessor along with each improved label so you can recover a route, not only a total. If totals tie, both routes are valid optima. A travel-time solution assumes the supplied times apply to the journey.

A longest walk may not exist

In a directed acyclic network, process vertices following the arrow order and keep the largest accumulated total arriving at each vertex to find a longest path. This works because a finite list of non-repeating directed routes is available.

If a positive-weight cycle can be repeated without restriction, no finite longest walk exists. Each extra circuit increases the total. State whether the network is acyclic or whether repeated vertices are prohibited; a shortest-path procedure cannot simply be reversed for every longest-route problem.

A common trap

The route with fewer edges must be shortest.

Instead: The labelled weights, not the number of edges, determine the total.

02 / WORKED EXAMPLES

See the thinking

Example 1

Find the shortest

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

The possible paths have totals $5 + 6 = 11$ , $5 + 2 + 7 = 14$ , and $3 + 6 + 7 = 16$ .
Choose the smallest.

A→C→E, weight 11.

Example 2

Find the longest

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

Use the same three possible paths.
The largest total is $3 + 6 + 7 = 16$ .

A→B→D→E, weight 16.

Check your understanding

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

Show answer

Every additional circuit adds weight.

The number of circuits has no upper bound.

03 / WORKSHEET

Your turn

6 questions · 12 marks · Work at your own pace.

Worksheet PDF 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…

Continue learning

Minimum spanning trees including Prim's algorithm

Next lesson

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 ↗

Back to Matrices and networks