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