**Assignment 04: Dijkstra's Algorithm and Data Structures**
*Due Thu Mar 25 11:00 PM Pacific Time*
[Back to Algorithms](http://cs.pomona.edu/classes/cs140/)
# Learning Goals
- Learn how to implement graph algorithms and use an adjacency list.
- Discover properties about heaps and how they relate to other data structures.
- Apply tree balancing with a Red-Black binary search tree.
- Compare different methods for implementing hash tables.
# Overview
This assignment includes two parts:
1. Answer the [question in this PDF](resources/Heaps-BSTs-HashTables.pdf). See section Resources for the PDF Questions for some help.
2. Write a program for the problem described in section Dijkstra's Single Source Shortest Path Algorithm (must be compatible with Python 3.8).
You may work on this assignment alone or with a partner. Please send me a message on Slack if you want me to assign you to work with a random partner. Whether you work alone or with a partner, only one partner will submit both parts to [gradescope](https://www.gradescope.com/).
Three key points for the hand written part:
1. you should either print the PDF and write your answers directly on the printed sheet, or add annotations to the PDF with Edge (Windows) or Preview (OSX) (using the correct format and spacing will help us grade),
2. ensure that the uploading partner adds the other partners after submission, and
3. **if you have any questions please ask them on [Slack](https://divisionii.slack.com/archives/G019H3HEXBK)**.
# Resources for the PDF Questions
For question `3(c)` you can use the formula found under "A simple exponentiation" at the [Wiki Page for the Birthday Problem](https://en.wikipedia.org/wiki/Birthday_problem).
For question `4`, you will find the following resources helpful:
- [Code Listing and Example](https://code.activestate.com/recipes/578375/)
- [GitHub Code Listing](https://github.com/ActiveState/code/blob/master/recipes/Python/578375_Proofofconcept_more_spaceefficient/recipe-578375.py)
- [StackOverflow Comment](https://stackoverflow.com/questions/39980323/are-dictionaries-ordered-in-python-3-6)
- [Python 3.6 News](https://docs.python.org/3.6/whatsnew/3.6.html#whatsnew36-compactdict)
- [Explanation in Blog Form](https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html)
- [Python-Dev Mailing List Conversation](https://mail.python.org/pipermail/python-dev/2016-September/146327.html)
# Example Execution
I always like to start by showing you the end result.
If you do not see an animation above this line (or if you see the animation but you don't see the progress bar), you will need to refresh the page (sometimes more than once). Or you can go directly to the player: https://asciinema.org/a/364437
**You can copy and past from the above animation!**
# Dijkstra's Single Source Shortest Path Algorithm
Your program will accept two program arguments: (1) a filename and (2) a start vertex number. Your program will output the shortest path from the start vertex to all other vertices.
## Input File
The file will include all of the information needed to create a **directed** graph.
The format of this file is referred to as an adjacency list. Here is an example of such a file:
~~~
1 2,1 8,2
2 1,1 3,1
3 2,1 4,1
4 3,1 5,1
5 4,1 6,1
6 5,1 7,1
7 6,1 8,1
8 7,1 1,2
~~~
Each line of the file contains the following information: a vertex identifier (a value from `1` through `n`) and then a list of edges where each edge contains a pair of values (the connecting vertex and an integer value for the edge weight).
For example, on the third line above (`3 2,1 4,1`) we can see that vertex `3` is connected to vertex `2` with a weight of `1`, and vertex `3` is also connected to vertex `4` with a weight of `1`. The graph for the above adjacency list is shown below:
**Although the above example only shows two edges per node, there can be any number of edges.** For example, look at the adjacency list below:
~~~
1 2,3 3,2
2 4,4
3 2,1 4,2 5,3
4 5,2 6,1
5 6,2
6 1,9
~~~
**Additionally, the spacing between edges might not be consistent.** Your program should handle any kind of whitespace between edges (i.e., multiple spaces and tabs).
## Your program
Your file must be named `dijkstras.py`.
You have two choices for your program:
1. Use the version found in the [Heap Slides (page 42)](https://cs.pomona.edu/classes/cs140/pdf/l22-heaps.pdf). You can get at most an 80% on the programming assignment by implementing this version.
2. Write a version using [this implementation of a Fibonacci Heap (`fibheap.py`)](resources/fibheap.py). You can get full credit on the programming assignment by implementing this version. See [this page created by Dr. Damon Wischik](https://www.cl.cam.ac.uk/teaching/2021/Algorithms/repo2/advdata.html) for additional help using his code.
In either case, you will need to follow these steps:
**Step 1**. Open the input file and read in the contents. I read the data into a Python dictionary where each *key* was a vertex identifier and each *value* was a list of edges. For instance, this is what my dictionary looks like for the example pictured above:
~~~
{
1: [(2, 1), (8, 2)],
2: [(1, 1), (3, 1)],
3: [(2, 1), (4, 1)],
4: [(3, 1), (5, 1)],
5: [(4, 1), (6, 1)],
6: [(5, 1), (7, 1)],
7: [(6, 1), (8, 1)],
8: [(7, 1), (1, 2)]
}
~~~
**Step 2.** Implement Dijkstra's SSSP Algorithm.
**Step 3.** Print all path lengths as a comma separated list. For instance, the correct output for the example graph (pictured above) starting at vertex 1 is:
~~~
0,1,2,3,4,4,3,2
~~~
# Submitting Your Assignment
You will submit your PDF assignment on [gradescope](https://gradescope.com/). **Only one partner should submit your PDF.** The submitter will add the other partner through the gradescope interface. You will also submit your code to gradescope.
You will submit your Python file to gradescope. **Only one partner should submit your code.** The submitter will add the other partner through the gradescope interface. Please add your names in comments at the top of the file.
To pass the autograder, your output must exactly match the expected output. You can use [text-compare](https://text-compare.com/) to compare your output to the expected output and that should give you an idea if you have a misspelled word or extra space (or if I do).
I've enabled a leaderboard for the assignment. You do not need to worry about it affecting your grade. I just thought it looked like a cute feature. Feel free to give yourself (your group) any name you'd like for the leaderboard.
Additional details for using gradescope can be found here:
- [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work)
- [Scanning Work on a Mobile Device](https://help.gradescope.com/article/0chl25eed3-student-scan-mobile-device)
- [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members)
- [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)