Implement a program that inputs a weighted directed graph, and finds the shortes

Question

Implement a program that inputs a weighted directed graph, and finds the shortest path between two given vertices of this graph. Your program must read a graph from a given file, prompt the user to specify two vertices, and output the shortest path between them. The format of the graph encoding is as follows:

<vertex> <vertex> <weight>

<vertex> <vertex> <weight>

<vertex> <vertex> <weight>

Explanation / Answer

#include #include using namespace std; // This class represents a directed graph using adjacency list representation class Graph { int V; // No. of vertices list *adj; // Pointer to an array containing adjacency lists public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph bool isReachable(int s, int d); // returns true if there is a path from s to d }; Graph::Graph(int V) { this->V = V; adj = new list [V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.