Finding the shortest path

• Print out copies of the worksheet to share with students.
• Confirm that computers are on, logged-in, and connected to the Internet

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.

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?

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:

1. 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.

2. 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.

3. 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.

4. 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

5. 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 Q1-Q5, 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:

1. Measure the distance to all the surrounding points and draw a line to the closest point.
2. Repeat step 1 until all points have been connected with a line.

If n is the number of points and l is the number of lines, then the pattern is lines = (n-1) + (n-2_ ) + (n-3) + ...+ (n-l) and the general formula is (n(n-1_ ))/2

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.

Activity:

Walk students through the following:

1. 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?
2. Open the Traveling Salesperson simulation.
3. Use the dropdown in the upper-right to set the region.
4. Use the "Sort by" dropdown in the upper-left to choose to sort the cities by Latitude, Longitude, or Randomly.
5. Press the green "Start road trip" button to begin the trip.
6. Once the road trip is complete
   1. Review the route on the map, does it look like an efficient route?
   2. In the table below, write the total distance traveled.
7. 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?

8. 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.
9. 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).

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 well-known 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?

Lesson Vocabulary

Computational Thinking Concepts