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:

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

Really abbreviated version

you can simply omit this lesson and you’ll survive

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.

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!

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

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.

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!