Please read the remarks about programming problems for this course.

Implement the dijkstra function that is part of the code found here. This function uses Dijkstra's single source shortest path algorithm to find the shortest path to all vertices.

All the support code is provided:

You do not have a lot of code to write for this assignment, but you will need to spend sometime to familiarize yourself with the infrastructure provided.

You may add helper functions if you like; for example, I wrote a find_min_unknown function to return the index of the vertex with known = false and minimum distance value from a VertexList.

You do not need to use a min-heap for the minimum vertex selection required by Dijkstra's algorithm. You may instead use a simple linear search.

The file graph1.txt contains the following text:

6 -1 10 -1 5 12 7 10 -1 2 2 -1 -1 -1 2 -1 3 -1 -1 5 2 3 -1 -1 1 12 -1 -1 -1 -1 4 7 -1 -1 1 4 -1

The first line of the file indicates the number of vertices in the graph. The next six lines represent the adjacency matrix, where -1 indicates no connection. A correctly implemented dijkstra function will result in the provided framework printing 

. 10  .  5 12  7
10  .  2  2  .  .
.  2  .  3  .  .
5  2  3  .  .  1
12  .  .  .  .  4
7  .  .  1  4  .
Node | Dist. | Path
-----+-------+--------
   0 |     0 | 0
   1 |     7 | 0 -> 3 -> 1
   2 |     8 | 0 -> 3 -> 2
   3 |     5 | 0 -> 3
   4 |    10 | 0 -> 3 -> 5 -> 4
   5 |     6 | 0 -> 3 -> 5

First it prints the adjacency matrix, then it prints the shortest path results. While this sample file is useful for testing your code, your function must work for any valid adjacency matrix with nonnegative edge weights.

You should not modify any existing code in the provided framework; simply complete the dijkstra function and possibly add one or more other helper functions.

When you are finished submit your dijkstra.cpp source file to eclass.e.southern.edu.