Flight schedules can be represented in a network. In the diagram above, cities (identified by their airport codes) are represented by vertices and direct flights between cities are represented by edges connecting those cities. There may be many combinations of flights that will take a traveller from one place to another. Computer programs can find a path that minimises the travel time and present it to the traveller.
This lesson investigates shortest path using Geogebra and worksheets, and applies similar techniques to identify the cheapest and the quickest route. Critical reflection on differences between minimum spanning tree and shortest path is also conducted.
In Lesson Four and Five, the students were introduced to concepts and methodologies of identifying minimum spanning tree. This lesson challenges students with a new concept in regard to network application, while also link it to previous lessons in order to give students a holistic view on network topic.
Students learn to:
applies network techniques to solve network problems MS1-12-8
chooses and uses appropriate technology effectively and recognises appropriate times for such use MS1-12-9
uses mathematical argument and reasoning to evaluate conclusions, communicating a position clearly to others MS1-12-10
Students find a shortest path from one place to another in a network with no more than 10 vertices
– identify a shortest path on a network diagram
– recognise a circumstance in which a shortest path is not necessarily the best path or contained in any minimum spanning tree
Communicating, Problem solving, Understanding
0 - 5
The teacher helps students to recall the definition of minimum spanning tree and states the goals of this lesson to students. [AFL]
Students participate in discussion.
5 - 20
The teacher uses Geogebra activity [ICT] to explore the shortest paths on different diagrams with students.
The teacher introduces students to Dijkstra's algorithm. Students work in pairs and follow the instruction on the worksheet to find the shortest path. The teacher then verify students' working in front of the classroom and shows more dynamic examples using Geogebra activity.
Reflection questions include: [AFL]
Q1: Is shortest path the same as minimum spanning tree? Are all vertices visited by the shortest path?
Q2: what constitutes the shortest path? Is ‘shortest’ the best word? Could it also be replaced with cheapest? Or lightest?
Q3: Is the shortest path always the quickest?
Answers:
Q1: No, no
Q2: The least number of edges or the least total weight between 2 vertices constitutes the shortest path. the shortest can be placed with the cheapest or the lightest.
Q3: The shortest path is not always the quickest, depending on other conditions that influence travelling time.
Students listen and participate in the conversation.
Students review the worksheet.
20 - 50
The teacher divides the students into 2 groups.
One group of students are instructed to investigate the cheapest way to travel between 2 cities using different forms of transport (via car, plane, uber, etc.). Students draw up weighted network where each vertex represents a suburb/station/airport and each edge represents the cost.
Another group of students find the fastest way to get to the 10 closest parks to their home. They need to consider if any of these paths are unrealistic or less desirable at different times of the day or year.
2 groups of students are required to share their investigation process in front of the class. The teacher poses reflection question such as 'is the shortest path the best path?' and let students to give the reasons of their answers.
Students follow teacher's instruction, investigate the scenario, and share their works and ideas in front of the class.
50 - 60
The teacher asks students to brainstorm the distinction between minimum spanning tree and shortest path. [AFL]
[Differentiation]
If the students are struggling in eliciting ideas, the teacher gives a scenario to students, and ask students to brainstorm the distinction between minimum spanning tree and shortest path in the given scenario: the mayor of a small outback town would like to upgrade the dirt tracks in the town to paved roads so that every home is connected to every other home by a paved road. The mayor has two choices: minimise the overall kilometres required (i.e. the cost) to find a minimum spanning tree or choose the roads to create a collection of shortest paths from the mayor’s house to every other home.
Answer: Via minimum spanning tree, the mayor uses the least pave stones to buid the path; Via shortest paths, the mayor is able to visit every other home by the shortest distance possible, but the number of pave stones are not the lowest.
Students brainstorm ideas and express their opinions.