For this assignment you will be implementing Dijkstra’s shortest path algorithm. Specifically, your program will output the distances of the shortest paths from vertex 1 to all other vertices.The in

For this assignment you will be implementing Dijkstra’s shortest path algorithm. Specifically, your program will output the distances of the shortest paths from vertex 1 to all other vertices.

The input file

Your programs will read a file, the name of which will be provided via a command line argument. 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 to n) and then a list of edge information where each edge contains a pair of values (the connecting vertex and an integer value for the edge length). 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 length of 1, and vertex 3 is also connected to vertex 4 with a length 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

Your program

As stated before you are allowed to write your programs in Python, C++, or Rust. Personally, I found this assignment quite a bit easier to do in Python. Your filename should be dijkstras.{py,cpp,rs}. You are required to write the names of all partners in comments at the top of the file.

You do not need to worry about using a Heap to reduce the running time (though you should give it a try if you have time), but instead implement the O(mn) version. This is a general outline for your program:

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 (you could do this with a std::map in C++). For instance, this is what my dictionary looks like for the example 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. Next you should initialize the two variables needed for Dijkstra’s algorithm: an array that holds all of the path lengths (if you prefer, you can initialize path lengths to 1000000 instead of infinity), and an initially empty set. For this assignment, your start vertex, s will always be vertex 1, so you should set the distance to vertex 1 to zero and add 1 to the set.

Step 3. In the next step you need to implement the loop in Dijkstra’s Algorithm. Remember, you will need to loop until every vertex has been visited (another way to say this is that you should loop until |your set| is equal to n). Here are the highlights of what this loop does:

• An edge (v,w) should only be considered if v is in your set and w is not.

• Thus, for each vertex already in your set you will need to check each of the vertices to which it is connected.

• Calculate Dijkstra’s greedy criterion for each of the considered edges and save the edge with the smallest value (the shortest path length).

• Add the appropriate vertex to your set and update the vertex’s path length.

Step 4. After the loop, you should print all path lengths as a comma separated list. For instance, the correct output for the example graph (above) is:

0,1,2,3,4,4,3,2

Notes for Python Programs

I am requiring you to include a shebang at the top of your file/script. If you are using Python3 your shebang will look like this:

#!/usr/bin/env python3

If you are using Python 2.7 you should use this:

#!/usr/bin/env python

These will make it easy for me to run your code regardless of which version of Python you choose to use. Remember, any comments that you add to your file should come below this shebang.