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

/* 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
0 4 6
5 0 2
3 7 0

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

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

2. Priyanka singh

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