← LearnYear 10 Maths · NetworksFree placement check
Year 10AC9M10SP03

Algorithms on Networks

Design, test and refine solutions to spatial problems using algorithms and digital tools; communicate and justify solutions.

An algorithm is a set of steps that always works, so you never have to be clever. Two are worth knowing: the cheapest route between two places, and the cheapest way to connect everything.

Builds onYr 10 · Networks and Connectedness

Method

An algorithm must terminate
Every run must end, and end with an answer. A rule that could loop forever is not an algorithm.
Shortest path is not fewest edges
A two-edge route can cost more than a three-edge one. Always add the weights.
Greedy means cheapest next, every time
At each step take the cheapest option available. Simple to run, and easy to justify.
A spanning tree has no loops
E=V−1E = V - 1
Connecting $V$ places always needs exactly $V-1$ edges. One more would create a loop and waste money.
Justify by comparing
A solution is only complete when you show the alternatives cost more.

Worked example

e.g. Five towns with the road costs shown. Find the cheapest route A→E, then the cheapest way to link all five.\text{Five towns with the road costs shown. Find the cheapest route } A \to E \text{, then the cheapest way to link all five.}
  1. Write the network out with every weight before you start.
    Weighted network of five towns A to E421583ABCDECosts in millions of rand
  2. Shortest path. List every route from A to E and total each one.ABDE=4+5+3=12ACDE=2+8+3=13ACBDE=2+1+5+3=11ABDE = 4+5+3 = 12 \qquad ACDE = 2+8+3 = 13 \qquad ACBDE = 2+1+5+3 = 11
  3. Choose the smallest total, not the fewest roads.ACBDE=11ACBDE = 11
    The cheapest A to E route highlighted through C and B421583ABCDECheapest route is 11, using four roads not three
  4. Cheapest connector. Now a different question: link all five towns for the least total cost.we need 5−1=4 roads\text{we need } 5 - 1 = 4 \text{ roads}
  5. Sort every road by cost, cheapest first.BC(1), AC(2), DE(3), AB(4), BD(5), CD(8)BC(1),\ AC(2),\ DE(3),\ AB(4),\ BD(5),\ CD(8)
  6. Take them in order, but skip any road that would form a loop.take BC, AC, DEskip AB (loop)take BD\text{take } BC,\ AC,\ DE \quad \text{skip } AB \text{ (loop)} \quad \text{take } BD
  7. Stop once you have V−1V-1 roads. Add the costs.1+2+3+5=111+2+3+5 = 11
    Minimum spanning tree using roads BC, AC, DE and BD421583ABCDECheapest connector: four roads, total 11
  8. Justify it. Say why the rejected road was rejected.AB was skipped because A,B,C were already joinedAB \text{ was skipped because } A,B,C \text{ were already joined}

Practice

Add weights, never count edges.

1
A route uses 2 roads costing 9 and 7. Another uses 4 roads costing 3, 2, 4 and 3. Which is cheaper?\text{A route uses 2 roads costing 9 and 7. Another uses 4 roads costing 3, 2, 4 and 3. Which is cheaper?}
Answer16 vs 12∴the four-road route16 \text{ vs } 12 \quad\therefore\quad \text{the four-road route}
2
How many edges are needed to connect 9 places with no loops?\text{How many edges are needed to connect 9 places with no loops?}
Answer9−1=89 - 1 = 8
3
While building a cheapest connector you reach a road joining two already-linked towns. What do you do?\text{While building a cheapest connector you reach a road joining two already-linked towns. What do you do?}
AnswerSkip it — it would form a loop and add cost without connecting anything new.\text{Skip it — it would form a loop and add cost without connecting anything new.}
4
Why is taking the cheapest road at every step enough to justify a cheapest connector?\text{Why is taking the cheapest road at every step enough to justify a cheapest connector?}
AnswerAny swap for a dearer road can only raise the total, so no cheaper set exists.\text{Any swap for a dearer road can only raise the total, so no cheaper set exists.}
5
A network has 6 vertices and 5 edges and is connected. Can it contain a loop?\text{A network has 6 vertices and 5 edges and is connected. Can it contain a loop?}
AnswerNo. 6−1=5, so it is exactly a spanning tree.\text{No. } 6-1 = 5 \text{, so it is exactly a spanning tree.}
6
Why must an algorithm be written so it always terminates?\text{Why must an algorithm be written so it always terminates?}
AnswerA procedure that can run forever never produces an answer, so it cannot be used to solve the problem.\text{A procedure that can run forever never produces an answer, so it cannot be used to solve the problem.}
Next step
Practise Algorithms on Networks with instant marking
A free 10-minute placement check finds which Year 10 topics to work on first, then Summit builds a weekly plan around them.
See where my child is →