Lesson 9

Weighted Networks & Shortest Path

Summary

Lesson Goals

By the end of the lesson, students should be able to:

Apply either Prim's algorithm or Kruskal's algorithm to determine the minimum spanning tree(s) of a given network
Calculate the weight of a minimum spanning tree
Suggest a plausible context for finding minimum spanning trees
Calculate the weight of a path by summing the weights of the included edges
Convert distance weight values to time weight values when given information about speed
Explain why the shortest path is not necessarily the best path

Use method of inspection to identify a shortest path from one vertex to another in simple directed networks
Produce network diagrams from real-world maps by adding appropriate vertices and edges
Explain the benefit of increasing the number of vertices and edges when finding a shortest path
Identify whether a shortest path is on a minimum spanning tree for a given network

Syllabus Content

N1.2: Shortest Paths

Students:

- find a shortest path from one place to another in a network with no more than 10 vertices AAM
  1. - 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

Working Mathematically

Represent networks in graphical form given real-world maps (Communicating)
Apply trial-and-error or method of inspection to find the shortest path between two vertices (Problem Solving, Fluency)
Solve problems related to finding the shortest path between two vertices, with additional constraints (Problem Solving, Understanding)
Calculate the total weight of the shortest path by summing the weights of the included edges (Fluency, Problem Solving)
Communicate the solution to a shortest path problem within a given context (Problem Solving, Communicating)
Explain why the shortest path may not be the best path (Reasoning, Justification)

Resources

Example Network Diagrams (for finding MST, see Orientation)
Whiteboard and Whiteboard Markers
Projector/Screen, Map Pictures (digital and A4 double-side printed, see Introduction)
Recording Sheet (see Body)
Alternate tasks: Forest Worded Description (printed as a small handout), Laptop (for Flight Connections website, see Body)
Homework Network Problem (see Homework/Follow-Up)

Strategies Used

Group & Class Work
Open-Ended Questions/Task
Differentiated Tasks
Class Discussion
Localised Content (Map)
ICT (Flight Connections website)
Scaffolding

New Vocabulary

Path

"A path in a network diagram is a walk in which all of the edges and all the vertices are different. A path that starts and finishes at different vertices is said to be open, while a path that starts and finishes at the same vertex is said to be closed. There may be multiple paths between the same two vertices."

"A shortest path in a network diagram is a path between two vertices in a network where the sum of the weights of its edges are minimised."

Image: shortest path shown using green vertices and black arrowheads

Lesson Details

Orientation

Working Mathematically: Communicating, Fluency

Diagram Task (7 min)

Before the lesson, print off the Example Network Diagrams document and cut each page in half (in total, there should be eight network diagrams with different weighted edges). Place a network diagram on each table group.

Once students have sat down, instruct them to practice applying either Prim's Algorithm or Kruskal's Algorithm to their table's network diagram in order to find its minimum spanning tree.

Students should first do this activity individually in their workbooks, then compare their results with their table group members.
Students should also determine whether their network diagram has multiple minimum spanning trees. If so, they should find and draw each of them.
Afterwards, a representative from each group goes to the whiteboard and redraws their diagram (with the edges that are part of the minimum spanning tree drawn in a different whiteboard marker colour). Students also calculate and write down the total weight of their minimum spanning tree (AFL).
Optional (if students finish early): Students should also come up with a plausible context for their network diagram, then share it with the class during discussion

Once each group has drawn their minimum spanning tree diagrams on the whiteboard, select a few groups to share which algorithm they used and explain the steps they took (AFL).

Example Network Diagrams - Details

Diagrams drawn in MS Paint; compiled in MS Word

Orientation Activity - MST.docx

Introduction

Working Mathematically: Fluency, Understanding, Problem Solving

Classroom Discussion (13 min) [NUM]

Display Picture 1 on a screen, and provide the following context for the introduction activity:

The teacher has forgotten to buy a chocolate cake for an upcoming lesson. They need to quickly travel to the nearest Woolworths to purchase one.

Once students understand the problem, ask them to consider the following question (that they will answer during the Body activity):

Which set of roads should I travel through to get from the high school to Woolworths in the shortest amount of time?

Display Picture 2 on a screen and, using annotation tools, label the vertices A to E (A - high school, E - Woolworths). Vertices B, C and D should represent road junctions. Provide each group with an A4-sized printed copy of this map (Picture 2 & 3 printed double-sided). Give each group some time to use their rulers to measure the distance of each edge between vertices (in total: 5 edges to assign weights to), and ask each group to shout out the distance for an edge when they have found it. Afterwards, ask students to explain what the weight of the edges could represent (e.g. driving distance) (AFL).

Scaffold students' analysis of the problem by asking the following questions: What is the driving distance between A and E if we travel through:

- the top route (A > B > C > E)
- the bottom route (A > B > D > C > E)

Afterwards, ask students if they are ready to decide which route the teacher should take to Woolworths (AFL).

- If ready - ask them to determine how long it would take to reach the destination using either route (they will not be able to unless given a speed)
- If not ready - allow students to ask for additional information (e.g. speed limits, traffic lights, pedestrians, road construction, weather, road quality, car or other modes of transport, quality of vehicle)

Prompt students to flip over their map (from Picture 2 to Picture 3) to reveal the colour-coded map. Explain that the teacher can only drive up to the speed limit of the road:

Red roads - 40 kilometres per hour (school zone)
Blue roads - 50 kilometres per hour
Green roads - 70 kilometres per hour

Allow students to discuss the following questions before holding a class discussion (AFL):

- Calculate the time it would take to travel either route if I drove at the speed limit on each road.
- Which route should the teacher take to get to the store in the shortest amount of time (legally)?

Map Routes - Details

Picture A

Map retrieved from Google Maps, and modified in Paint.net (with added roads); scale determined using FreeMapTools (measured real-world distance then compared with printed version of map)
Recommended: recreate using a map of your school/local area

Picture B

There are two routes from Sefton High School to Woolworths Chester Hill. The top route is shorter in distance than the bottom route.
Map Scale - 1cm : ~50m

Picture C

Road speed limits marked by colourRed roads: 40 kph / Blue roads: 50 kph / Green roads: 70 kph
With these additional constraints, the bottom route from Sefton High School to Woolworths Chester Hill is faster than the top route

Picture D

Blank version of the map with roads colour-coded (speed limits); for use during Body Activity

Body

Working Mathematically: Problem Solving, Communicating, Reasoning

Group Map Analysis (30 min) [NUM]

Present a new challenge for the students: for each table group, provide a portable whiteboard and whiteboard markers, and a ruler if students do not have one already. Instruct students to find the most optimal route between the school and the shops (by travelling along the pre-existing roads).

- Students will need to use rulers (and the provided scale) to make distance measurements, as well as the colour key code (each road has a specific speed limit) to determine the maximum speed allowed and therefore the time needed to travel down a road
- Students should redraw the map as a network diagram on the portable whiteboard. Students are encouraged to add new intermediary vertices (and connect them using the roads on the map as edges). They should place new vertices at the junctions of intersecting roads.
- Students can decide how many vertices they want to include (and as a result, how many paths there are to consider).

Explain to students as they do the activity that they are demonstrating the process that Google/Apple Maps uses to find optimal paths between two places.

For strategies for helping students, see Advice/Differentiation Opportunities.

After 25 minutes, instruct each group to share their work, including what path they found to be the shortest, as well as comment on interesting findings (e.g. the effect of adding more vertices) (AFL).

Other Contexts (Differentiation)

Easier Context:
Forest - the table group are hikers walking through a national park (format: written description)

(The numbers provided can and should be changed) There are 7 locations at the National Park: the campground (at the entrance), picnic area, public bathrooms, cafe, lake, cave and a ranger tower

The campground is 100m away from the public bathrooms, 150m from the picnic area and 2km from the ranger tower
The picnic area is 2.5km away from the ranger tower and 4km from the cafe
The public bathrooms are 2km away from the ranger tower and 3km from the lake
The cafe is 2.5km away from the ranger tower and 2.5km from the cave entrance
The lake is 2km away from the ranger tower and 2.5km from the cave entrance
The cave entrance is 4km away from the ranger tower
The ranger tower is at the centre of the national park, connected to every location around it by a dirt road or path

Students should use the information to draw a network diagram on their portable whiteboard, then pick pairs of locations to find the shortest path between them. These paths (and their weights) should be recorded on the Recording Sheet handout (AFL).

Slightly Harder Context:
Flight Connections - https://www.flightconnections.com/route-map-qantas-qf (format: map)

Key locations: Sydney, Canberra, Melbourne, Hobart, Adelaide, Perth, Darwin, Brisbane, Auckland

Students should click on each of these locations and determine which flight connections are available to other key locations. Students should record the available flight connections (and their distance) on a separate network diagram drawn on a portable whiteboard. Afterwards, students should pick pairs of locations to find the shortest path between them. These paths (and their weights) should be recorded on the Recording Sheet handout (AFL).

Additionally, students should comment on the possible differences in their results if they were to instead consider flight time (rather than distance) (AFL).

Recording Sheet - Details

Created in MS Word; example recording table (can be rewritten on a whiteboard or in students' workbooks)

Shortest Path Recording Table.docx

Bonus Teacher Notes

Check what Google/Apple maps suggest as the best route between the school and store (for the provided example, with no map modifications, it is the bottom route)

Google Maps (Phone App) shows the speed limit for each road

Advice/Differentiation Opportunities

Offer students the choice to choose a different network problem/context based on their current skill level.
If students are not comfortable with the large-scale drawing, encourage them to try re-drawing it in their workbooks.
Depending on your class, limit the number of vertices students add to their diagrams.
Additionally, you can limit the number of edges so that students do not produce complete (and therefore more complicated) graphs.
Scaffolding - if students are struggling, scaffold the process of finding shortest path (A --> B, A --> C, A --> D).

Conclusion - 10 min

Working Mathematically: Fluency, Reasoning

Class Discussion (10 min)

At the end of the lesson, ask each group to draw the minimum spanning tree for their network, using Prim’s or Kruskal’s Algorithm (see Lessons 7 and 8).

Ask the class to consider if the shortest path between two of their vertices (e.g. the school and the shops) was in the minimum spanning tree, and If not, speculate why this might be the case (AFL)?

Homework/Follow-Up

Remind students to update their Trip Log if they have not already, as well as to continue working on their presentation project for the final lesson of the unit (AOL).

Homework:

Instruct students to copy the Homework Network Problem into their workbooks, or to check Google Classroom for a digital copy.

Task: Select three pairs of vertices (must be on different islands) and record the shortest path between them (including the total weight of the path).

Students should submit their responses to the teacher either at the start of the next lesson, or through Google Classroom (AFL).

Homework Network Problem - Details

Created in MS Paint

Previous Lesson

Next Lesson

Google Sites

Report abuse