Shortest Path Algo

Write a program that implements the weighted single-source shortest-path algorithm with positive edge costs(Dijkstras Algorithm), vertices designated by integers 1 to N, and integer weights.

The vertex class may/should have the following data members:

vector< int> adj; // Adjacency list
vector< int> w; // Edge weights
int dist; // Distance from source
int path; // Predecessor on path from source

Include :

• a main function that stores the graph,
• an interactive user to print
  • all possible simple paths (the path does not contain any vertex twice)
  • the shortest path from any source vertex to any other vertex

The graph should be read from a file with the following format:

************graph1.dat***************
3
1 2 5
1 3 7
3 2 1
*************************************

The first line indicates the total number of vertices (|V| = 3) The following lines represent a directed edge with an edge. For example, 1 2 5 means there is an edge (1,2) and the weight is 5.