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.
