Description
Graph Representation You will read a directed graph from a text file. Below is an example: Graph1.txt 5 0 1 0.2 3 10.1 4 0.5 -1 1 0 1.5 -1 2 1 100.0 3 50.2 -1 3 -1 4 1 10.5 2 13.9 -1 The first line is the number of vertices � (= 5 in this example). Each vertex is represented by an integer from 0 to � − 1. For each vertex you have a list of the adjacent vertices with positive edge weights. Each list terminates with -1 to indicate the end of the line. For instance, in the above example, vertex 0 is connected to vertex 1 (edge weight 0.2), to vertex 3 (edge weight 10.1) and to vertex 4 (edge weight 0.5). Represent a graph using an adjacency list. Read the vertices and edges from a text file. Dijkstra’s Algorithm Implement Dijkstra’s Algorithm using a priority queue. Write a program that runs as follows: findPaths This program should use Dijkstra’s Algorithm to find the shortest paths from a given starting vertex to all vertices in the graph file. The program should then continuously prompt the user to specify a target vertex. It will then print the sequence of vertices along the shortest path from the starting vertex to the target vertex as well as the total cost of the path.
