electrofriends.com > Source Codes > Software Programs > C++ Programs > Data structure > C++ program to implement dynamic programming algorithm to solve the all pairs shortest path problem

C++ program to implement dynamic programming algorithm to solve the all pairs shortest path problem

Share on FacebookTweet about this on TwitterDigg thisPin on PinterestShare on LinkedInShare on StumbleUponShare on TumblrShare on Google+Email this to someone

/* Write a C++ program to implement dynamic programming algorithm to solve the all pairs shortest path problem */

#include<iostream>
#include<conio.h>
using namespace std;
int min(int a,int b);
int cost[10][10],a[10][10],i,j,k,c;
 
main()
{
  int n,m;
  cout <<"enter no of vertices";
  cin >> n;
  cout <<"enter no od edges";
  cin >> m;
  cout<<"enter the\nEDGE Cost\n";
for(k=1;k<=m;k++)
{
cin>>i>>j>>c;
a[i][j]=cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(a[i][j]== 0 && i !=j)
a[i][j]=31999;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
cout <<"Resultant adj matrix\n";
for(i=1;i<=n;i++)
{
for( j=1;j<=n;j++)
  {
  if(a[i][j] !=31999)
  cout << a[i][j] <<" ";
  }
cout <<"\n";
}
getch();
}
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}

OUTPUT

enter no of vertices3
enter no od edges5
enter the
EDGE Cost
1 2 4
2 1 6
1 3 11
3 1 3
2 3 2
Resultant adj matrix
0 4 6
5 0 2
3 7 0

Share on FacebookTweet about this on TwitterDigg thisPin on PinterestShare on LinkedInShare on StumbleUponShare on TumblrShare on Google+Email this to someone

Related Posts

Ranjith

Site Admin

Read More About this author

7 Responses to “C++ program to implement dynamic programming algorithm to solve the all pairs shortest path problem”

  7. Priyanka singh

    I want details of this program bcoz m nt able to understand it………

    Reply

Leave a Reply