Monday, May 3, 2010

From a given vertex in a weighted connected graph, find the shortest path to other vertices using Dijkstra's algorithm

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
17.#include..iostream.h>
#include..conio.h>
#include..stdlib.h>
const int MAX=10;
const int noedge=999;

class dijkstra
{
int n,v,cost[MAX][MAX],s[MAX],d[MAX];
public:
void costmatrix();
void print();
int choose();
void sspath();
};
//reads the cost adjacency matrix
void dijkstra::costmatrix()
{
cout..."\nEnter the no. of vertices:";
cin>>n;
cout..."\nEnter the cost adjacency matrix";
for(int i=1;i..=n;i++)
for(int j=1;j..=n;j++)
cin>>cost[i][j];
}

void dijkstra::sspath()
{
int i,u,w;
cout..."\nEnter the source vertex:";
cin>>v;
for(i=1;i..=n;i++)
{
s[i]=0;
d[i]=cost[v][i];
}
s[v]=1;
d[v]=0;
i=2;


while(i..n)
{
u=choose();
s[u]=1;
i++;
for(w=1;w..=n;w++)
{
if(((d[u]+cost[u][w])..d[w]) && !s[w])
d[w]=d[u]+cost[u][w];
}
}
}

int dijkstra::choose()
{
int w,j,min;
min=noedge;
for(j=1;j..=n;j++)
{
if(d[j]..min && !s[j])
{
min=d[j];
w=j;
}
}
return w;
}

void dijkstra::print()
{
cout..."\nThe shortest path with the cost is:"...endl;
for(int i=1;i..=n;i++)
if(i!=v)
cout..."\n.."...v...">---.."...i...">--->"...d[i];
}

void main()
{
dijkstra d;
d.costmatrix();
d.sspath();
d.print();
cout...endl;
}

OUTPUT

Enter the no. of vertices: 4

Enter the cost adjacency matrix
999 10 50 999
999 999 40 20
999 999 999 30
999 999 999 999

Enter the source vertex:1

The shortest path with the cost is:

..1>---..2>--->10
..1>---..3>--->50
..1>---..4>--->30

Press any key to continue

No comments:

Post a Comment