Resources For Teachers For Tutors For Students & Parents Pricing
Create Free Account
Year 10 Maths - 10A Networks

Shortest Paths and Weighted Networks

20 practice questions 0 video lessons Theory + worked examples
Practice 20 questions
Practice questions

Every question with a fully worked solution.

Start practising
Create a free accountTrack your progress and save your work as you go.
Create free account

Theory

In a weighted network each edge has a number: a distance, a time or a cost. This Year 10A maths page shows how to find the shortest path between two vertices, by comparing routes or by working out the shortest distance to each vertex in turn, and how to handle compulsory stops, closed roads and unknown weights.

A weighted network has a number, called a weight, on each edge. The weight might be a distance in km, a travel time in minutes or a cost in dollars.

The length (or weight) of a path is the sum of the weights of its edges. The shortest path between two vertices is the path with the smallest total. "Shortest" can mean quickest or cheapest, depending on the weights.

The shortest path is not always the direct edge, and not always the path with the fewest edges. Two short edges can beat one long one.

For small networks, list the routes and compare. For bigger networks, find the shortest distance from the start to each vertex in turn, closest first, and write it beside the vertex. The value at the finish is the answer, and tracing back gives the route.

A weighted network where the direct edge is not shortestTriangle ABC with weights AB 7, BC 6 and AC 15. Going through B costs 13, less than the direct edge of 15. 7615ABC A–B–C = 7 + 6 = 13 A–C = 15
The numbers on the edges are weights (distance, time or cost). The direct edge is not always the shortest route.
Shortest distances written at each vertexNetwork with AB 3, AC 6, BC 2, BD 7 and CD 3. Boxed shortest distances from A: A 0, B 3, C 5 (through B), D 8 (through B and C). 36273ABCD 0 3 5 8
Write the shortest distance from \(A\) in a box at each vertex, working outwards. \(C\) gets \(5\) (through \(B\)), not \(6\).

Length of a path:

\[\text{length of a path} = \text{sum of the weights of its edges}\]
length=∑weights

Shortest distance to a vertex \(V\) when it can be reached from \(X\) or \(Y\):

\[d(V) = \min\big(d(X) + XV,\ d(Y) + YV\big)\]
d(V)=min(d(X)+XV,d(Y)+YV)
Must pass through a vertex. Split the trip there: shortest from the start to the stop, plus shortest from the stop to the finish.
Closed road. Delete that edge and solve again. The answer can only stay the same or get longer.
Unknown weight \(x\). Write the route containing \(x\) as an expression and compare it with the best route that avoids it, using \(<\) or \(>\).

Comparing routes (small networks)

  1. List every sensible route from the start to the finish. Do not revisit a vertex.
  2. Add the weights along each route.
  3. Choose the smallest total, and name the route.

Working outwards (larger networks)

  1. Write \(0\) at the start.
  2. Label the vertex that is closest to the start with its shortest distance.
  3. Repeat: for each next vertex, add each edge weight to the label it comes from, and keep the smallest.
  4. Stop when the finish is labelled. Trace back along the edges that gave each smallest value to find the route.
Example 1 — Comparing routes
Find the shortest path from \(A\) to \(E\) and its length.
Solution
Weighted network from A to EEdges: AB 7, AC 3, BC 2, BD 5, CD 8, DE 4 and BE 11. The shortest path A, C, B, D, E is highlighted. 73258411ABCDE

List the sensible routes and add the weights.

\(A - B - E\)\(=\)\(7 + 11 = 18\)
\(A - B - D - E\)\(=\)\(7 + 5 + 4 = 16\)
\(A - C - D - E\)\(=\)\(3 + 8 + 4 = 15\)
\(A - C - B - D - E\)\(=\)\(3 + 2 + 5 + 4 = \mathbf{14}\)
3+2+5+4=14

The shortest path is \(A - C - B - D - E\), length 14. It has the most edges but the smallest total.

Example 2 — Working outwards
The network shows walking tracks in km. Find the shortest distance from \(S\) to \(T\) and the route.
Solution
Walking tracks with shortest distances from STracks in km: SP 2.0, SQ 1.2, PQ 0.6, PR 2.2, QU 2.5, PU 2.0, RU 0.7, RT 1.6, UT 2.4. Boxed shortest distances from S: Q 1.2, P 1.8, U 3.7, R 4.0, T 5.6. The path S, Q, P, R, T is highlighted. 2.01.20.62.22.52.00.71.62.4SPQRUT 0 1.8 1.2 4 3.7 5.6

Find the shortest distance from \(S\) to each vertex in turn, closest first. At each vertex, take the smallest of the ways in.

\(Q\)\(=\)\(1.2\)
\(P\)\(=\)\(\min(2.0,\ 1.2 + 0.6) = 1.8\)
\(U\)\(=\)\(\min(1.2 + 2.5,\ 1.8 + 2.0) = 3.7\)
\(R\)\(=\)\(\min(1.8 + 2.2,\ 3.7 + 0.7) = 4.0\)
\(T\)\(=\)\(\min(4.0 + 1.6,\ 3.7 + 2.4) = \mathbf{5.6}\)
T=4.0+1.6=5.6

Trace back from \(T\): \(T \leftarrow R \leftarrow P \leftarrow Q \leftarrow S\). The route is \(S - Q - P - R - T\), 5.6 km.

Example 3 — A compulsory stop
Ella drives from home \(H\) to the beach \(B\) but must stop at the shop \(S\). Times are in minutes.
(i) Find her quickest route and time.
(ii) How much time does the stop add?
Solution
Travel times from home to the beach via the shopTimes in minutes: HJ 6, HS 9, JS 4, JK 7, SK 5, KB 7, SB 15, JB 20. The route H, S, K, B through the shop S is highlighted. 6947571520HJSKB

(i) Split the trip at the shop and find the quickest way for each part.

\(H \to S\)\(\)\(\min(9,\ 6 + 4) = 9\)
\(S \to B\)\(\)\(\min(15,\ 5 + 7,\ 4 + 7 + 7) = 12\)
\(\text{total}\)\(=\)\(9 + 12 = \mathbf{21}\text{ min}\)

Route: \(H - S - K - B\).

(ii) Without the stop, the quickest is \(H - J - K - B = 6 + 7 + 7 = 20\) min. The stop adds 1 minute.

9+12=21
Example 4 — An unknown weight
The direct road \(P - Q\) has length \(x\) km, a whole number. The shortest route from \(P\) to \(Q\) goes through \(R\). Find the smallest possible value of \(x\).
Solution
Network with an unknown direct roadRoads: PR 7, RQ 6, PS 5, SQ 9 and the direct road PQ of length x. 7659xPRSQ
\(P - R - Q\)\(=\)\(7 + 6 = 13\)
\(P - S - Q\)\(=\)\(5 + 9 = 14\)

For the route through \(R\) to be the shortest, the direct road must be longer than \(13\).

\(x\)\(>\)\(13\)
\(x\)\(=\)\(\mathbf{14}\ \text{(smallest whole number)}\)
x>13

Check: with \(x = 13\) the direct road would tie with \(P - R - Q\), so \(13\) does not work.

Common pitfalls

The direct edge is not always shortest. Check routes through other vertices. A detour through two short edges often wins.
Fewest edges is not shortest. Add the weights; do not count edges.
Do not stop at the first route you find. A route that looks sensible may not be the smallest. Compare all the reasonable ones, or label every vertex.
Keep the units. Weights can be km, minutes or dollars. Give the answer in the same unit, and the route as well as the total if asked.

Frequently asked questions

How do you find the shortest path in a network?

For a small network, list the possible routes, add the weights on each, and choose the smallest total. For a larger network, find the shortest distance from the start to each vertex in turn until you reach the finish.

What is a weighted network?

A network where every edge has a number on it, such as a distance, a time or a cost. The weight of a path is the sum of the numbers on its edges.

Is the shortest path always the one with the fewest edges?

No. A path with more edges can have a smaller total if those edges are short. Always add the weights.

How do you find the shortest path if you must stop somewhere on the way?

Split the trip at the stop. Find the shortest path from the start to the stop and from the stop to the finish, then add them.

What happens to the shortest path if a road is closed?

Remove that edge and find the shortest path again. It stays the same if the closed road was not on it; otherwise the new shortest path is the same length (if another route tied) or longer.

More in Networks
Networks and Network Diagrams
20 questions
Connectedness, Euler Trails and Circuits
20 questions