# '15-'16 Algorithms - Shortest Path Problem **URL:** \ **Category:** Unit and Lesson Discussion\ **Tags:** csp-unit-1\ **Created:** [June 15, 2015, 4:16pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643 "2015-06-15T16:16:38Z")\ **Posts on this page:** 12\ **Page:** 1
**Author:** ![jessica\_opaleski\_for](https://avatars.discourse-cdn.com/v4/letter/j/77aa72/32.png) [@jessica\_opaleski\_for](https://forum.code.org/u/jessica_opaleski_for)\ **Post date:** [June 15, 2015, 4:16pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/1 "2015-06-15T16:16:38Z")
## 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 🙂 - 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.** _ ---
**Author:** ![mstahl](https://avatars.discourse-cdn.com/v4/letter/m/977dab/32.png) [@mstahl](https://forum.code.org/u/mstahl)\ **Post date:** [September 26, 2015, 6:13pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/2 "2015-09-26T18:13:23Z")
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. ---
**Author:** ![brook](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/brook/32/88_2.png) [@brook](https://forum.code.org/u/brook)\ **Post date:** [September 26, 2015, 9:44pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/3 "2015-09-26T21:44:50Z")
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. ---
**Author:** ![jeb9682](https://avatars.discourse-cdn.com/v4/letter/j/b77776/32.png) [@jeb9682](https://forum.code.org/u/jeb9682)\ **Post date:** [November 9, 2015, 7:58pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/4 "2015-11-09T19:58:04Z")
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! ---
**Author:** ![brook](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/brook/32/88_2.png) [@brook](https://forum.code.org/u/brook)\ **Post date:** [November 10, 2015, 3:52pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/5 "2015-11-10T15:52:15Z")
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). ---
**Author:** ![gjschmidt](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/gjschmidt/32/4922_2.png) [@gjschmidt](https://forum.code.org/u/gjschmidt)\ **Post date:** [November 17, 2015, 3:38pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/6 "2015-11-17T15:38:05Z")
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. ---
**Author:** ![brook](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/brook/32/88_2.png) [@brook](https://forum.code.org/u/brook)\ **Post date:** [November 17, 2015, 4:31pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/7 "2015-11-17T16:31:33Z")
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” ---
**Author:** ![katherine\_pomeroy](https://avatars.discourse-cdn.com/v4/letter/k/a8b319/32.png) [@katherine\_pomeroy](https://forum.code.org/u/katherine_pomeroy)\ **Post date:** [November 17, 2015, 8:40pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/8 "2015-11-17T20:40:13Z")
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! ---
**Author:** ![andrea\_m\_robertson1](https://avatars.discourse-cdn.com/v4/letter/a/a698b9/32.png) [@andrea\_m\_robertson1](https://forum.code.org/u/andrea_m_robertson1)\ **Post date:** [November 18, 2015, 1:06pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/9 "2015-11-18T13:06:03Z")
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 ---
**Author:** ![dani](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/dani/32/285_2.png) [@dani](https://forum.code.org/u/dani)\ **Post date:** [November 18, 2015, 2:18pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/10 "2015-11-18T14:18:39Z")
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 ---
**Author:** ![dani](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/dani/32/285_2.png) [@dani](https://forum.code.org/u/dani)\ **Post date:** [November 18, 2015, 2:19pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/11 "2015-11-18T14:19:12Z")
Hi Andrea, Great catch! That definitely should go through E instead of G. I have updated the KEY. -Dani ---
**Author:** ![brook](https://sea2.discourse-cdn.com/flex016/user_avatar/forum.code.org/brook/32/88_2.png) [@brook](https://forum.code.org/u/brook)\ **Post date:** [September 28, 2016, 2:14pm UTC](https://forum.code.org/t/15-16-algorithms-shortest-path-problem/643/12 "2016-09-28T14:14:14Z")