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.

Calculate the price of your order

550 words
We'll send you the first draft for approval by September 11, 2018 at 10:52 AM
Total price:
$26
The price is based on these factors:
Academic level
Number of pages
Urgency
Basic features
  • Free title page and bibliography
  • Unlimited revisions
  • Plagiarism-free guarantee
  • Money-back guarantee
  • 24/7 support
On-demand options
  • Writer’s samples
  • Part-by-part delivery
  • Overnight delivery
  • Copies of used sources
  • Expert Proofreading
Paper format
  • 275 words per page
  • 12 pt Arial/Times New Roman
  • Double line spacing
  • Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Our guarantees

Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

Money-back guarantee

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read more

Zero-plagiarism guarantee

Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read more

Free-revision policy

Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read more

Privacy policy

Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read more

Fair-cooperation guarantee

By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more