Answer must be in C++ Assignment: For this week\'s assignment, you\'ll be making
ID: 3680143 • Letter: A
Question
Answer must be in C++
Assignment: For this week's assignment, you'll be making a program that can compute the shortest distance between two selected points on a graph. Your previous program which can multiply matrices, and your knowledge of adjacency matrices should let you do this. There are FIVE DIFFERENT graphs provided with this assignment see attached document), and for each of the five graphs, you have to find the shortest distance between the points given below. PLEASE NOTE: As some graphs have one-way paths, you'll realize the distance from A to B will not always be the same as the distance from B to A. You do NOT need to tell me paths you have to cross to get from one point to another. So your results could say "3 steps is the shortest distance or 15 steps" or so on. FOR YOUR ASSIGNMENT For each of the five graphs, find the shortest distances between the following points. (1) A to B (2) B to A. (3) A to C (4) B to C (5) C to DExplanation / Answer
#include <iostream>
#include <list>
using namespace std;
class Graph
{
int V;
list<int> *adj;
public:
Graph(int V);
void addEdge(int v, int w);
bool isReachable(int s, int d);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int> [V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
bool Graph::isReachable(int s, int d)
{
if (s == d)
return true;
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
list<int> queue;
visited[s] = true;
queue.push_back(s);
list<int>::iterator i;
while (!queue.empty())
{
s = queue.front();
queue.pop_front();
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (*i == d)
return true;
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
return false;
}
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Enter the source and destination vertices: (0-3)";
int u, v;
cin >> u >> v;
if (g.isReachable(u, v))
cout << " There is a path from " << u << " to " << v;
else
cout << " There is no path from " << u << " to " << v;
int temp;
temp = u;
u = v;
v = temp;
if (g.isReachable(u, v))
cout << " There is a path from " << u << " to " << v;
else
cout << " There is no path from " << u << " to " << v;
return 0;
}