IN C++ please Problem: Given a directed weighted graph, write a program to gener
ID: 3728058 • Letter: I
Question
IN C++ please
Problem: Given a directed weighted graph, write a program to generate single source shortest paths based on Dijkstra’s algorithm.
Inputs: 1.The edges and their associated weights of a weighted graph are stored in an external text file, where each line is of the following format:The first line is a pair of integers, V and E, denoting the number of vertices and edgesof the graph. Followed by lines denoting the edges of the graph.
V E // V an integer denoting number of vertices and E denoting number of edges
vi vj wij // where vi and vj are integers and wij is a real number // the direction is from vi to vj2.
Interactive inputs: your program should start with the following menu. (1) Open input files.// prompt the user to enter a file name. (2) Source for shortest paths.//Prompt to enter a source vertex denoted by an integer in the range of 1 to |V|(3) Paths from A to B. (Bonus: 15pts) Ask user to enter verticesA and B, then list all paths and thetotal distancefor // each path, from A to B.(4) Quit.
Outputs: Print to screen the following results:Print vertices of each shortest path and its distance from the source.
Testing: create your testing data files
Explanation / Answer
This is a C++ Program to find the shortest path in linear time. This can be done by using Dijkstra’a Shortestpath algorithm.
Here is source code of the C++ Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// Data structure to store graph edges
struct Edge {
int source, dest, weight;
};
// data structure to store heap nodes
struct Node {
int vertex, weight;
};
// class to represent a graph object
class Graph
{
public:
// An array of vectors to represent adjacency list
vector<Edge> *adjList;
// Constructor
Graph(vector<Edge> const &edges, int N)
{
// allocate memory
adjList = new vector<Edge>[N];
// add edges to the undirected graph
for (Edge const &edge: edges)
{
// insert at end
adjList[edge.source].push_back(edge);
}
}
// Destructor
~Graph() {
delete[] adjList;
}
};
void print_route(vector<int> const &prev, int i)
{
if (i < 0)
return;
print_route(prev, prev[i]);
cout << i << " ";
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(const Node &lhs, const Node &rhs) const
{
return lhs.weight > rhs.weight;
}
};
// Run Dijkstra's algorithm on given graph
void shortestPath(Graph const& graph, int source, int N)
{
// create min heap and push source node having distance 0
priority_queue<Node, vector<Node>, comp> min_heap;
min_heap.push({source, 0});
// set infinite distance from source to v initially
vector<int> dist(N, INT_MAX);
// distance from source to itself is zero
dist[source] = 0;
// boolean array to track vertices for which minimum
// cost is already found
vector<bool> done(N, false);
done[0] = true;
// stores predecessor of a vertex (to print path)
vector<int> prev(N, -1);
// run till min_heap is not empty
while (!min_heap.empty())
{
// Remove and return best vertex
Node node = min_heap.top();
min_heap.pop();
// get vertex number
int u = node.vertex;
// do for each neighbor v of u
for (auto i : graph.adjList[u])
{
int v = i.dest;
int weight = i.weight;
// Relaxation step
if (!done[v] && (dist[u] + weight) < dist[v])
{
dist[v] = dist[u] + weight;
prev[v] = u;
min_heap.push({v, dist[v]});
}
}
// marked vertex u as done so it will not get picked up again
done[u] = true;
}
for (int i = 1; i < N; ++i)
{
cout << "Path from vertex 0 to vertex " << i << " has minimum "
"cost of " << dist[i] << " and the route is [ ";
print_route(prev, i);
cout << "] ";
}
}
// main function
int main()
{
// initialize edges as per above diagram
vector<Edge> edges =
{
{0, 1, 10}, {0, 4, 3}, {1, 2, 2}, {1, 4, 4}, {2, 3, 9},
{3, 2, 7}, {4, 1, 1}, {4, 2, 8}, {4, 3, 2}
};
// Number of nodes in the graph
int N = 5;
// construct graph
Graph graph(edges, N);
shortestPath(graph, 0, N);
return 0;
}
output: