Dijkstra's Algorithm provides the shortest path from a starting point in a graph to every other point in a graph. It does so by selecting the next closest vertex to the start and updating the list of distances as new vertices are visited.

Modify your existing Graph code to include Dijkstra's Algorithm for finding the shortest distance between vertices.

Add code to the main.cpp to accept as input, the name of a file. Read from the file the number of vertices and the edges between vertices, including edge weights and construct an adjacency graph. The file will contain a positive integer on the first line that represents the number of vertices in the graph. Each of the subsequent lines will contain three values that represent a single edge in the graph; the from vertex, the to vertex, and the non$-$negative weight. These edges are directed and will always be between valid vertices.

Provide code to read in these edges and construct an adjacency matrix for this graph.

For example, the file input$1.$txt contains:

$9$

$014$

$078$

$104$

$128$

$1711$

$218$

$237$

$254$

$282$

$327$

$349$

$3514$

$439$

$4510$

$524$

$5314$

$5410$

$562$

$652$

$671$

$686$

$708$

$7111$

$761$

$787$

$822$

$866$

$877$

This corresponds to the adjacency matrix:

$--4----------8--$

$4--8--------11--$

$--8--7--4----2$

$----7--914------$

$------9--10------$

$----41410--2----$

$----------2--16$

$--811------1--7$

$----2------67--$

Then, take as inputs a starting vertex for the algorithm, provide the distances, and show the path.

Vertex Distance Path

$000$

$140->1$

$2120->1->2$

$3190->1->2->3$

$4210->7->6->5->4$

$5110->7->6->5$

$690->7->6$

$780->7$

$8140->1->2->8$