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

Thursday, March 11th, 2010

/* 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

Avatar of Ranjith

Author Name :
Ranjith

Total : 7 Comments

Simillar Posts

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

  1. Jaro says:
    September 25, 2010 at 1:19 pm

    i want graph coloring coding in c++.Could u plz help in writing it plz.

  2. Adris says:
    November 25, 2010 at 10:58 pm

    thanks!

  3. prabakaran.m says:
    April 5, 2011 at 10:54 pm

    good

  4. sagar says:
    March 14, 2012 at 3:04 pm

    plsss give some description

  5. sagar says:
    March 14, 2012 at 3:04 pm

    i m not able to understand it

  6. sagar sulakhe says:
    March 14, 2012 at 3:05 pm

    Please tell me details regarding this program.

  7. Priyanka singh says:
    November 10, 2012 at 10:26 am

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

Leave a Reply

Question and Answer
C/C++ Unix & Linux Wordpress
Source codes
C C++ Java

Free email signup

Email: