'15-'16 Algorithms - Shortest Path Problem

CS Principles Unit and Lesson Discussion
1

NOTE from the Curriculum Author:

This lesson about Dijkstra’s shortest path algorithm is a tough lesson. Please note that the shortest path algorithm is NOT required knowledge for the AP exam. The intent of the lesson is to show students a real algorithm in pseudocode and to have them trace the algorithm out. However, the algorithm takes a while to understand fully and may take more time than you have.

Big Picture: The purpose of these algorithm detour lessons is to expose students to the challenges of writing out clear instructions to solve problems. Most students will not have seen or considered problems like these ones on graphs and they can be quite challenging, but they are interesting and visual.

If you do not want to teach the full lesson a few options for you are:

  1. Abbreviated Version
  • Have students study the the shortest path problem on the small graph diagrams provided in the first worksheet
  • Write down an algorithm in plain language (similar to the previous lesson on minimum spanning tree).
  • Have students look up Dijkstra’s algorithm on the web and see if they can see similarities between their solution and the “real thing”
  • Wrap up: talk about the differences between the minimum spanning tree problem and shortest path
  1. Really abbreviated version
  • you can simply omit this lesson and you’ll survive :slight_smile:
  • If you omit the lesson you’ll need to do more work on the front end of the next lesson How Routers Learn to make sure students understand the shortest path problem so they can appreciate how routers figure it out.

Use this thread to discuss your questions and comments about how to run the lesson.

2

What is the correct answer for bubble two “shortest tree path from selected node?” I thought it was B but the correct answer is given as A.

3

the correct answer is A, because that’s the graph with the shortest path from the source to all other nodes in the tree.

option b is not correct because the path from source to the bottom-right node costs 7, and in option a it only costs 6.

4

is the answer key correct for shortest path ? They ask for A to C in the instructions but it appears that the answer key connects all the nodes… Please help! Thanks!

5

hi, jason!

we’ve updated the language on the intro activity-- students should FIRST identify the shortest path from A-to-C on all of the graphs, THEN, they should go back to the graph and find the shortest paths from A to B, D, and E (note that this will not change the shortest path from A to C-- it will just result in building out the paths to the other nodes on the graph).

6

What’s the answer to question 4 in stage 7 and what format should the answer be in to be accepted? None of my students have been able to get an answer accepted.

7

hi, george!

the correct answer is 43 (10 nodes + 33 edges – because dijkstra’s must visit every node and edge once).

in order to get it correct, students should just enter “43”

8

Is there any guidance as to which node to go to first if 2 of them both have the lowest distance
from the current node? I assume it doesn’t matter… but it’s confusing having no mention of it in the algorithm. Thanks!

9

For Student Graph D in the answer key, can someone explain to me why the shortest path from D to F goes through G instead of E?

Andrea

10

Hi Katherine,

I don’t think it matters which one you pick. I’ll check into if the algorithm should mention it somewhere.

Thanks

Dani

11

Hi Andrea,

Great catch! That definitely should go through E instead of G. I have updated the KEY.

-Dani