Produce a program with the following capabilities. The program will prompt for t

Question

Produce a program with the following capabilities. The program will prompt for the start- ing vertex in the range of 0-9999. The program will then prompt for a different vertex in the range of 0-9999. The program will then execute a shortest path algorithm (Dijkstra’s is fine but you are welcome to use a different one). If a path does exist between the two vertices it will output the sequence of vertices in the shortest path, as well as the total weight of the entire path between the two vertices.

2 Extra Credit Problem

The above dataset is a test dataset for graph algorithms. While it does accomplish the goal of learning how to use graph algorithms in code, it doesn’t accomplish the goal of being a real world example. For extra credit you are welcome to produce your own dataset (of ample size 1000+ nodes) and use a shortest path algorithm or any other algorithm discussed in class on that graph. A good source for this may be the Open Street Map http://www.openstreetmap.org. If you do the extra credit you do NOT need to do the original problem but the program will be the same, that is given 2 vertices (different way to declare vertices would be okay here) as input and outputs the shortest path between them if it exists. If you are doing a minimum spanning tree specify so and give an example run through of your program. I have some ideas for how we could get some meaningful graphs from the OSM files you can download from the website. You could also use a subset of the IMDB database and do a 7 degrees of Kevin Bacon. If you are planning on doing this please talk to me and we can work out the details of your submission. You are welcome to look around for another dataset. The only requirements for this are that is a real world problem and that it has over 1000 nodes. Please do check with me first that your dataset meets the requirements.

i am strugling to do this assignment i will appricaited if one can help this assignment in c++ languege

Explanation / Answer

#include<iostream>
#include<conio.h>
#include<stdio.h>
using namespace std;
int shortest(int ,int);
int cost[10][10],dist[20],i,j,n,k,m,S[20],v,totcost,path[20],p;
main()
{
int c;
cout <<"Enter no of vertices";
cin >> n;
cout <<"Enter no of edges";
cin >>m;
cout <<" Enter EDGE Cost ";
for(k=1;k<=m;k++)
{
cin >> i >> j >>c;
cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
cout <<"enter initial vertex";
cin >>v;
cout << v<<" ";
cout << "Shortest paht is: " << endl;
shortest(v,n);
}

int shortest(int v,int n)
{
int min;
for(i=1;i<=n;i++)
{
S[i]=0;
dist[i]=cost[v][i];
}
path[++p]=v;
S[v]=1;
dist[v]=0;
for(i=2;i<=n-1;i++)
{
k=-1;
min=31999;
for(j=1;j<=n;j++)
{
if(dist[j]<min && S[j]!=1)
{
min=dist[j];
k=j;
}
}
if(cost[v][k]<=dist[k])
p=1;
path[++p]=k;
for(j=1;j<=p;j++)
cout<<path[j];
cout <<" ";
//cout <<k;
S[k]=1;
for(j=1;j<=n;j++)
if(cost[k][j]!=31999 && dist[j]>=dist[k]+cost[k][j] && S[j]!=1)
dist[j]=dist[k]+cost[k][j];
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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