Write a program to find the all pairs shortest path for a given graph
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u;
void main()
{ clrscr();
int m,c;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES Cost\n";
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<<”\n*****prim’s algorithm*****”;
cout <<"\nORDER OF VISITED VERTICES";
k=1;
while(k<n)
{
m=31999;
if(k==1)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(cost[i][j]<m)
{
m=cost[i][j];
u=i;
}
}
else
{
for(j=n;j>=1;j–)
if(cost[v][j]<m && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stk[top]=j;
top++;
m=cost[v][j];
u=j;
}
Getch();
}
cost[v][u]=31999;
v=u;
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}
OUTPUT:
Write a program to find the shortest distance from the source node to every other node Matrix Chain Multiplication PRESENTATION