Write a program in C or C++ that reads a file with a graph G=(V,E) with n nodes
ID: 3765535 • Letter: W
Question
Write a program in C or C++ that reads a file with a graph G=(V,E) with n nodes and the cost associated with every edge. The form of the file is the following:
n % the number of nodes
m % the number of edges
n1 n2 c1% where, n1 n2 identifies the edge between nodes n1 and n2 while c1 is the cost of the edge e.g.:
5
12
0 1 75
0 2 120
1 0 75
1 2 75
1 3 120
1 4 30
2 0 120
2 1 75
3 1 120
3 4 60
4 3 60
4 1 30
Your program should ask the user to enter the start node and the destination node (both integers) and it should output the shortest path (should show the sequence of nodes and minimum cost) from the start node to the destination node. This should be repeated until the user enters as start and destination the same node number.
Explanation / Answer
#include<stdio.h>
#include<conio.h>
int main()
{
int shpath[4][4],x[4][4];
int i,j,min,index,n,k;
printf(“enter number of paths”);
printf(enter start node”);
printf(“enter the destination node”);
printf(“enter the cost matrix”);
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
scanf(“&d”,a[i][j]);
for(i=1;i<=4;i++)
for(j=1;j<=4;j++)
printf(“enter no of nodes”);
scanf("%d",&value);
insert_data(value);
display();
count_node();
k[i]=0;
for(j=1;j<=4;j++)
{
int z,a;
z=shpath[i][j+1];
k[i]=k[i]+a[z][a];
if[z==k];
else
z==a;
index=sh;
for(i=1;i<=n;i++)
{
if(min>k[i])
{
min=k[i];
index=i;
}
}
printf(“shortest path”);
getch();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.