Graph Algorithms

For this programming assignment, you will implement a Graph using an adjacency list representation. Your program will read a graph from a file called graph.txt. The file is a text file where the first line contains two numbers. The first is the number of vertices n and the second is the number of edges m. After this line there will be m lines with three numbers. The first two numbers represent the source and destination vertex for the undirected edge. The third number is the weight for that edge. The final line of the file contains two numbers representing the index of two numbers. Your program should construct the graph and run Dijkstra�s shortest path algorithm. An example file would be4 5
0 2 1
1 2 5
2 3 3
1 3 2
0 3 10
0 3
This file represents a graph with 4 vertices, 6 edges, and has edges (0,2) with weight 1, (1,2) with weight 5, (2,3) with weight 3, (1,3) with weight 2, (0,3) with weight 10. Your program should output the shortest path between vertex 0 and vertex 3 as a sequence of vertex labels (0, 2, 3 in this example). NOTE: The weight does NOT have to be an integer. In general the weight will be a floating point number.
Powered by