Finding the shortest path
About this lesson
In this lesson, students will experiment with different ways of creating a path between two points with algorithm design and generalizing patterns. From the patterns, they will be able to generate an algorithm for efficiently traveling through cities in a region.
Year band: 78
Curriculum LinksCurriculum Links
Links with Digital Technologies Curriculum Area
Strand  Content Description 

Processes and Production Skills 
Define and decompose realworld problems taking into account functional requirements and economic, environmental, social, technical and usability constraints (ACTDIP027) Design algorithms represented diagrammatically and in English, and trace algorithms to predict output for a given input and to identify errors (ACTDIP029) 
Links with Mathematics Curriculum Area
Strand  Content Description 

Number and algebra: Patterns and algebra 
Create algebraic expressions and evaluate them by substituting a given value for each variable (ACMNA176) 
Learning sequence
 Preparation
 Learning hook: How to get there? (5 minutes)
 Learning input: Factors involved when choosing a route (5 minutes)
 Learning construction: Developing a strategy for traversing all points (20 minutes)
 Learning demonstration: Designing a road trip (30 minutes)
 Learning reflection: Refining an algorithm based on new constraints (10 minutes)
 Additional information and resources
Preparation
 Print out copies of the worksheet to share with students.
 Confirm that computers are on, loggedin, and connected to the Internet
Learning hook: How to get there? (5 minutes)
In this activity, students will consider how to get to a particular destination from their current location.
Choose a familiar location for students to consider the best way to get to the destination. Students share their ideas.
Use an online mapping tool to enter the destination and current location to check which route is suggested. Compare to student suggestions.
Learning input: Factors involved when choosing a route (5 minutes)
In this activity, students will consider the factors involved in choosing a route when traveling. Breaking down the challenge into smaller parts so they can understand it will help students solve larger problems later.
Activity:
Students respond to the following prompts:
Prompt 1: If you are traveling from one place to another, how do you decide what route to take? What are the factors that influence your decision?
Prompt 2: Imagine you were asked to create a road trip with multiple stops, how would you decide what route to take?
Notes to the teacher:
Students’ answers will vary depending on mode of transportation chosen based on the distance, the purpose of their trip (commuting to school vs a road trip), the time they need to get there, whether they are traveling with friends, etc.
Learning construction: Developing a strategy for traversing all points (20 minutes)
In this activity, students will develop strategies for drawing a route to all points in a grid using the shortest path they can find. Students will discover what steps produce the ideal results and produce an algorithm that can be used by others.
Activity:
Handout the worksheet: Shortest path
Walk students through the following:

In the drawing below are a set of points. Using a ruler and a pencil, try to draw the shortest route you can that connects all of the points. As you draw each line, keep track of the length of each line so you know how long your route is.
Q1: How did you decide which route to take? Do you think you could have taken a shorter path?

Try to find the shortest path using the grid below. The dots are in the same place but instead of drawing diagonal lines between two points, your route can only follow the grid lines. Keep track of the distance traveled as you draw your path.
Q2: How did you decide which path to take given that you had to stay on the grid lines?

Try to find the shortest path using the network below. The dots are in the same place as before but the only paths between them are the lines. Keep track of the distance traveled as you draw your path.
Q3: How did you decide which path to take given that you had to stay on the network lines?
 What was your total distance for each path? Rank the difficulty of developing a path for each one where 1 is the easiest and 3 is the most difficult.
Type Total Distance Traveled Difficulty (1 = easy, 3 = hard) Dots Grid Network 
Is there a pattern or equation that enables you to predict the number of lines that could directly connect all of the points in a set? It may help to start with the diagrams below and determine how many lines could all the points in each set.
Assessment:
For Q1Q5, students’ answers will vary. They should try to develop their answers so that they can articulate the steps they used to determine the path. If they chose the steps randomly, that is fine, but encourage them to try another method. Their process could look like:
 Measure the distance to all the surrounding points and draw a line to the closest point.
 Repeat step 1 until all points have been connected with a line.
Number of points  Number of lines 

2  1 
3  3 
4  6 
5  10 
6  15 
If n is the number of points and l is the number of lines, then the pattern is lines = (n1) + (n2_ ) + (n3) + ...+ (nl) and the general formula is (n(n1_ ))/2
Learning demonstration: Designing a road trip (30 minutes)
In this activity, students will develop a method or algorithm to make a road trip as efficiently as possible. Students can iterate on their algorithm in order to generalize patterns.
Notes to the teacher:
This activity is similar to a wellknown computer science problem known as the Traveling Salesperson problem except that in the simulation there is no requirement that they must return to the origin. In the Learning reflection activity, students will be asked to think whether they would need to change their approach if this constraint was added.
Activity:
Walk students through the following:
 In the earlier task, you developed ideas for how you might decide to take a road trip around a region in the most efficient way. Look back at your original ideas and the previous activity. Do you still feel that is the best way or would you change it?
 Open the Traveling Salesperson simulation.
 Use the dropdown in the upperright to set the region.
 Use the "Sort by" dropdown in the upperleft to choose to sort the cities by Latitude, Longitude, or Randomly.
 Press the green "Start road trip" button to begin the trip.
 Once the road trip is complete
 Review the route on the map, does it look like an efficient route?
 In the table below, write the total distance traveled.
 Try another sorting method (i.e. if you tried Latitude, try Longitude) and run the simulation. Record the total distance traveled. How does this method compare to the previous attempt?
Q1: In the previous activity, you developed a path between a set of points, a grid of points, and a network of points. Which of the three ways is this method of traveling most similar to?
 Switch the sorting method to "Draggable" so you can refine one of the existing sorting methods or implement your own strategy. Run the simulation, record the result, and compare it to previous attempts.
 Try your method with another region to see if your method works only for one or multiple regions.
Trial Region Sorting method (Latitude / Longitude / Random / Write your Own Method Distance Traveled (meters) 1 2 3 4 5
Assessment:
This activity is similar to connecting a network of points since the paths to travel are roads so you are not free to take any path you chose (set of points), nor are the points connected by straight lines of equal distance (grid of points).
Learning reflection: Refining an algorithm based on new constraints (10 minutes)
In this activity, students will reflect on how well their process for making the shortest path worked and what they might change as new constraints were added.
Activity:
Students respond to the following prompts:
Prompt 1:
What are some insights you had while trying to develop a process for traveling the shortest distance, whether it was dots on a piece of paper or cities on a map?
Prompt 2:
The road trip simulation is a simplified version of a wellknown computer science problem known as the Traveling Salesman problem. How would your algorithm for traveling the shortest path between cities change if the additional requirement was added that you must return to the city that you started from?
Additional information and resources
Lesson Vocabulary
Term  Definition  For Additional Information 

Latitude  The geographic coordinate that specifies the northsouth position of a point on the Earth's surface.  https://en.wikipedia.org/wiki/Latitude 
Longitude  The geographic coordinate that specifies the eastwest position of a point on the Earth's surface.  https://en.wikipedia.org/wiki/Longitude 
Computational Thinking Concepts
Concept  Definition 

Algorithm Design  Creating an ordered series of instructions for solving similar problems 
Pattern Generalization  Creating models of observed patterns to test predicted outcomes 