CS 302 Assignment 7:

Due date: Friday, November 30, 2018, midnight.

1. Write a program which implements Dijkstra's algorithm for the single source minimum path problem on a weighted directed graph with no negative weights.
3. Here is the suggested outline of your program.
   Read a weighted directed graph from your directory. Copy a small graph to get started.
   1. The first line of the file is an integer giving n, the number of vertices of the graph. The vertices of the graph will be named 0 ... n-1. The source vertexi is 0.
   2. You will need an array to hold the vertices.
   3. Each of the remaining lines encodes one arc.
   4. The line "i j w" encodes an arc (i,j) of weight w.
   5. All weights will be non-negative integers. Store the edges a an array of outneighbor lists. I suggest using linked The outneighborlist for node i consists of nodes each of which must have at least two integer, the name of the neighbor and the weight of the arc.
   6. Implement an updatable min-queue. The items on that queue are vertices which are partially processed.
   7. In the array of vertices, each vertex must store its id, an integer between 0 and n-1, its distance to the source vertex, and its back pointer, as well as the linked list of its outneighbors.
   8. Initially, the queue contains exactly the source vertex.
   9. At each step:
      1. Delete the item of minimum distance in the queue. Call that i; i is now finished.
      2. For each outneighbor j of i, there are four possibilities.
         j is fully processed: do nothing.
         j is partially processed and no shorter path from 0 to j is found: Do nothing.
         j is partially processed and there is a shorter path from 0 to j which is through i: Update the value of dist, set the value of back to i.
         j is unprocessed: Insert j into the queue and assign its distance, and let back be i.
      3. Write the shortest path from 0 to i for each vertex i.
4. Your program must be written in C++ and must run on bobby.cs.unlv.edu.
5. My output files for the two smaller graphs show every step of the algorithm. But if I do the same thing for the larger graph, the output has 1040187 lines. You don't want to do that. The assignment does not require printing out every step, although it's a useful debugging tool.