For this week’s assignment, you’ll be making a program that can compute the shor

Question

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 –WHAT- the path is (don’t say ‘A to R to G to F to B’). For this assignment we only want the distance. Distance is considered the number of 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 D

Answer in C++

Explanation / Answer

#include <stdio.h>
#include <queue>
#include <conio.h>
using namespace std;

int nodes, edges, src, dest;
int graph[100][100], color[100],distance[100],prev[100];
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;

int main() {
printf("Nodes, edges, source, destination? ");
scanf("%d %d %d %d", &nodes, &edges, &src, &dest);
for (int i = 1; i <= edges; i++) {
printf("Edge %d: ", i);
int x, y;
scanf("%d %d", &x, &y);
graph[x][y] = 1;
}

//run BFS
queue<int> q; //create a queue
q.push(src); //1. put root node on the queue
do {
int u = q.front(); //2. pull a node from the beginning of the queue
q.pop();
printf("%d ", u); //print the node
for (int i = 1; i <= nodes; i++) { //4. get all the adjacent nodes
if ((graph[u][i] == 1) //if an edge exists between these two nodes,
&& (color[i] == WHITE)) { //and this adjacent node is still WHITE,
q.push(i); //4. push this node into the queue
color[i] = GRAY; prev[i] = u; //color this adjacent node with GRAY
}
}
color[u] = BLACK; //color the current node black to mark it as dequeued
} while (!q.empty()); //5. if the queue is empty, then all the nodes have been visited
for(int i=10;i<=0; i--)
{if (prev[i] == 0)
{ }
else
printf("%d -> ", prev[i]); }
getch();
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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