High School Computer Science and Programming Workshop -- Class 11

Here is a direct link to Snap!

To play with Snap! you can just click on the play button on some of the images, like the one above. If you have any problems with it loading, visit Snap! directly in a new browser tab (On that page, click "Run Snap! now"). Another possible solution, if your browser is not Chrome, is to give Chrome a try.

Exercise: Implement the Shortest-Path Algorithm

In this class we'll implement in Snap! the Shortest-Path Algorithm that we learned during the last class.

Here is again our working example graph:

And here is the pseudocode for the Shortest-Path Algorithm, from Wikipedia:

I have started it for you, creating our working example graph here, setting up sprites representing each vertex and each edge. Explore the program. Clicking on the big green button should run the Shortest-Path Algorithm, which is left for you to implement:

Here is a direct link to this exercise.

Notice I have already initiated the my Prev variable for each vertex to be set to nothing, and my Dist value to be 0 for the source vertex S and to be 999 (representing infinity) for all other vertices. Also the Q variable (which holds the set of remaining vertices) and the U variable (which records the current vertex being visited) from the algorithm are set properly to start the algorithm.

So go ahead and give it a try! Your job is to translate the pseudocode given above into a script for the big green button. It should properly set the value of the shortest-path variable to be a list of vertices in the shortest path, thus it must start with S and end with T.

This is not an easy exercise, but try your best to get it working. Afterwards, If you want to compare your final work, here is a link to the complete program.