implement all pair shortest path using dynamic programming algorithm-programmingraja

 Aim: Write a program to implement all pair shortest path using dynamic programming algorithm.

Software used: DevC++

Description: 

In this Programming we initialize the solution matrix same as the input graph matrix as a first step. Then we update the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and updates all shortest paths which include the picked vertex as an intermediate vertex in the shortest path.

Program coding:-

#include<iostream>

#include<iomanip>

#define NODE 7

#define INF 999

using namespace std;

intcostMat[NODE][NODE] = 

{

   {0, 3, 6, INF, INF, INF, INF},

   {3, 0, 2, 1, INF, INF, INF},

   {6, 2, 0, 1, 4, 2, INF},

   {INF, 1, 1, 0, 2, INF, 4},

   {INF, INF, 4, 2, 0, 2, 1},

   {INF, INF, 2, INF, 2, 0, 1},

   {INF, INF, INF, 4, 1, 1, 0}

};

voidfloydWarshal(){

int cost[NODE][NODE]; 

for(int i = 0; i<NODE; i++)

for(int j = 0; j<NODE; j++)

cost[i][j] = costMat[i][j]; 

for(int k = 0; k<NODE; k++){

for(int i = 0; i<NODE; i++)

for(int j = 0; j<NODE; j++)

if(cost[i][k]+cost[k][j] < cost[i][j])

cost[i][j] = cost[i][k]+cost[k][j];

   }

cout<< "The matrix:" <<endl;

for(int i = 0; i<NODE; i++){

for(int j = 0; j<NODE; j++)

cout<<setw(3) << cost[i][j];

cout<<endl;

   }

}

int main(){

floydWarshal();

}

Output:-