Embedded Files
Summary
Summary
Lesson Goals
Lesson Goals
By the end of the lesson, students should be able to:
By the end of the lesson, students should be able to:
Construct simple weighted network diagrams with 5-8 vertices
Use method of inspection to find the shortest path between two specified vertices in a given network diagram
Calculate the length of different paths between two vertices
Apply Dijkstra's Algorithm to identify the shortest path from one vertex to another in a network of 10 vertices
Explain whether the shortest path is always the best path to travel along
Identify whether the shortest path is always contained in the minimum spanning tree of a network diagram
Syllabus Content
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
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
Working Mathematically
Represent networks in graphical form given real-world maps (Communicating, Fluency)
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, Communicating)
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
Resources
Paper or Index Cards, a Box, and a way for assigning students numbers (for Orientation)
Whiteboard and Whiteboard Markers
Chalk or Masking Tape or Rope
Plastic Cones, Sticky Tape and Printed Letters (see Introduction)
Courtyard/Basketball Court/Oval (somewhere that can be drawn or taped over, large space; could also use hall-space if available for an hour)
Method of generating edge weights (e.g. trundle wheel for distance measurement, or random number generator like a pair of six-sided dice)
Workbooks, Pens and Paper for students
Index Cards for Exit Task (see Conclusion)
Strategies Used
Strategies Used
Group & Class Work
Embodied Learning/Physical Activity
Open-Ended Questions
Class Discussion
Differentiated Learning
New Vocabulary
New Vocabulary
Dijkstra's Algorithm
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path between two vertices for a connected weighted network graph.
Video: Example of applying Dijkstra's Algorithm (to a directed weighted network)
Dijkstra's Algorithm (Summarised)
Adapted from Anthony Henderson's Introduction to Graph Theory from MATH2069Dijkstra's Algorithm (Summarised)
Given a weighted graph and a starting vertex (e.g. A), Dijkstra's Algorithm assigns temporary labels (e.g. 2, 3, 4) to every vertex, which are possibly changed in the course of the algorithm until they are declared to be permanent (e.g. [0], [3], [7]). The steps are:
Give the starting vertex (A) the permanent label [0]
If every vertex has a permanent label, stop the algorithm.
Otherwise, let v be the vertex that has most recently acquired a permanent label [L]
For every vertex w that is adjacent (connected with an edge) to vertex v, do the following:
if w has a permanent label, leave it unchanged
if w has no label, give it the temporary label equal to L + the distance from v to w
If w already has a temporary label K, compare K with L + the distance from v to w, and change the label to L + the distance from v to w if that is smaller than K
Of all the vertices that have temporary labels, choose one whose label is smallest, and make that the permanent label of that vertex.
Return to Step (2).
Lesson Details
Lesson Details
Orientation
Orientation
Working Mathematically: Communicating, Problem-Solving, Fluency
Peer-developed questions (10 min) [NUM]
Students are each given half of an A4-sized piece of paper (or an index card) with an ID number on the back (e.g. 1, 2, 3, ..., 30). Write on the whiteboard the following prompt for students to complete:
Draw a small weighted network diagram with 5-8 vertices.
The vertices should be connected together in such a way that the diagram (including the weights) is clear to read.
Specify a starting and finish vertex (e.g. Start: A, Finish: E).
Memorise or record the number on the back of your diagram.
Submit your finished diagram to the box at the front of the classroom.
Prepare a box on a chair or table for students to submit their diagram drawings once completed. Assign each student a new number (e.g. on the spot, picking numbered balls or paddle-pop sticks out of a hat, etc.). Hand out the diagrams to students (according to their new number) and instruct them to spend time finding the shortest path between the starting and finishing vertices specified by the diagram's author.
Once done, students can discuss their diagrams and solutions with their table groups. Each group selects one diagram that they feel is the most interesting and submits it to the front of the classroom (redraw on the whiteboard, label with the diagram's number). Alternatively, if portable whiteboards are available for each table group, redraw on those. Afterwards, each group explains how they found the shortest path for the diagram given to them (AFL). Have the original authors reveal themselves.
Introduction
Introduction
Working Mathematically: Communicating, Fluency
Outdoor Diagram Drawing (10 min)
Before the lesson, prepare a class set of chalk (or masking tape) and a portable whiteboard. When ready, hand each group a set and take the class, with their workbooks and a pen, outside of the classroom (either to a courtyard, basketball court or hall).
Note: An oval area could also work, but will require rope (to act as edges).
Instructions for Body Activity 1: As a class, negotiate and work together to draw a network diagram with ten vertices. Advise students of the following conditions for their diagram:
The class may connect the vertices together however they want, as long as the diagram is clear and easy to read (not too simple though).
No multiple edges or loops are allowed.
The network diagram should be sufficiently large enough for students to walk along and around; suitable for a large class of 20 to 30 students.
Each vertex should be labelled A to J (using plastic cones with paper labels taped on).
What A, B, C, ..., J represent is up to the class to decide - e.g. they can come up with town names starting with each letter.
Using a random number generator (e.g dice) or using a trundle wheel (to measure the actual distance between vertices), assign each edge a weight.
Label the edges using chalk, writing on a piece of paper (and taping it nearby), or by using large plastic playing cards.
Paper Labels - Details
Created in MS Word; print off and cut in half, then tape to plastic conesPaper Labels - Details
Cone Labels.docxBody 1
Body 1
Working Mathematically: Problem-Solving, Communicating, Fluency
Group Map Analysis (10 min) [NUM]
Once the class has completed their network diagram, explain the context of the activity: the class has created a map of a city and connected all of the suburbs together with roads. Today, we're interested in getting from A to J. Discuss the following question (AFL):
What do we care about the most when planning a drive to somewhere? Shortest path (or distance).
Instruct students to form their groups of four and to have an attempt at finding a short path from A to J in 5 minutes. Students are encouraged to try different strategies, including trial and error, or some form of elimination process.
After the 5 minutes are over, ask each group to present their shortest path, by walking along the network diagram, as well as share their strategy for finding it (AFL). Record the walk length of each group on a piece of paper or portable whiteboard. Once each group has presented, determine which group had the shortest path and instruct them to redraw their path on the whiteboard (and also to write down the total weight of their path) (AFL).
Advice/Differentiation Opportunities
Advice/Differentiation Opportunities
If students are not comfortable with the large-scale drawing, ask them to try re-drawing it in their workbooks.
Depending on your class, alter the number of vertices included in the diagram (recommended minimum 5, maximum 10).
Additionally, you can limit the number of edges so that students do not produce complete (and therefore more complicated) graphs.
Recording Sheet - Details
Created in MS Word; example recording table (can be rewritten on a whiteboard)Recording Sheet - Details
Example Recording Table.docxBody 2
Body 2
Working Mathematically: Communicating, Reasoning, Fluency
Class Outdoor Modelling Activity (25 min)
Introduce Dijkstra's Algorithm as one method of finding the shortest path:
Ask for ten volunteers to stand at each vertex with a piece of paper and a marker. Students will use the piece of paper to write down the temporary and permanent labels (in terms of the shortest walk from the starting vertex to their vertex).
Once students are ready, go through the process with the remainder of the class:
Redraw the diagram on a portable whiteboard, and show students how to appropriately label the diagram when using Dijkstra's Algorithm; instruct the volunteers to write their labels on their paper in the same way.
If there's time - get each group to use the algorithm to find the shortest path between another pair of vertices (not A and J). Discuss the following questions before wrapping up (AFL):
Is the shortest path always the best path? Why or why not?
Is the shortest path always contained in the minimum spanning tree? Why or why not?
E.g. a direct path from A to J (through an edge connecting the two) may weigh a significant amount, and so would not be included in any MST. However, it may be the shortest path compared to other paths that go through multiple vertices.
Teacher Advice: It will be important here that there are not too many edges. It may be wise to limit the number of edges students can draw. You could restrict students from crossing edges over one another. You can also reduce the number of vertices to a more manageable number.
Dijkstra's Algorithm (Summarised)
Adapted from Anthony Henderson's Introduction to Graph Theory from MATH2069Dijkstra's Algorithm (Summarised)
Given a weighted graph and a starting vertex (e.g. A), Dijkstra's Algorithm assigns temporary labels (e.g. 2, 3, 4) to every vertex, which are possibly changed in the course of the algorithm until they are declared to be permanent (e.g. [0], [3], [7]). The steps are:
Give the starting vertex (A) the permanent label [0]
If every vertex has a permanent label, stop the algorithm.
Otherwise, let v be the vertex that has most recently acquired a permanent label [L]
For every vertex w that is adjacent (connected with an edge) to vertex v, do the following:
if w has a permanent label, leave it unchanged
if w has no label, give it the temporary label equal to L + the distance from v to w
If w already has a temporary label K, compare K with L + the distance from v to w, and change the label to L + the distance from v to w if that is smaller than K
Of all the vertices that have temporary labels, choose one whose label is smallest, and make that the permanent label of that vertex.
Return to Step (2).
Conclusion
Conclusion
Working Mathematically: Understanding. Fluency
Class Discussion & Exit Task (5 min)
Discuss the following question: In what other contexts might finding the shortest path between two vertices in networks be useful (AFL)?
Exit Task:
Draw a simple (5 vertices) weighted network diagram on the whiteboard and instruct students to apply Dijkstra's Algorithm to find the shortest path between vertices A and E (see Exit Task Diagram for an example).
Students submit their working and the final weight of their shortest path (AFL).
Exit Task Diagram (Example) - Details
Created in MS Paint; demonstrates Dijkstra's algorithm (in red)Exit Task Diagram (Example) - Details
Homework/Follow-Up
Homework/Follow-Up
Students should update their Trip Log (Dijkstra's Algorithm), including writing out the steps for Dijkstra's Algorithm (AOL).
Remind students of Assessment Day (conclusion of the Networks & Paths unit).
Next lesson should occur after the weekend, in order to give groups the opportunity to include Shortest Path in their assessment.
Google Sites
Report abuse