Modify the following Floyd-Warshall algorithm by introducing a π(pi) table as per the class’s discussion. Here you can write one function named as generatePiTable(int g[][V])
.....................................................................................
#include <stdio.h>
#define V 4
#define INF 99999
#define NIL 0
void warshallAlgo(int g[][V]){
int i,j,k;
for(k=0;k<V;k++){
for(i=0;i<V;i++){
for(j=0;j<V;j++){
if(g[i][k]+g[k][j]<g[i][j]){
g[i][j]=g[i][k]+g[k][j];
}
}
}
}
printSols(g);
generatePiTable(g);
}
void printSols(int g[][V]){
printf("The matrix for shortest distance: \n");
for(int i=0;i<V;i++) {
for(int j=0;j<V;j++){
if(g[i][j]==INF){
printf("%5s","INF");
}
else{
printf("%5d",g[i][j]);
}
}
printf("\n");
}
}
void generatePiTable(int g[][V]){
printf("\nThe pi table is as follows: \n");
int pi[V][V];
for(int i=0;i<V;i++){
for(int j=0;j<V;j++){
if(g[i][j]==NIL || g[i][j]==INF){
pi[i][j]=NIL;
}
else{
pi[i][j]=i+1;
}
}
}
for(int i=0;i<V;i++){
for(int j=0;j<V;j++){
if (pi[i][j] == INF || pi[i][j] == NIL){
printf("%5s","NIL");
}
else{
printf("%5d",pi[i][j]);
}
}
printf("\n");
}
}
int main(){
int g[V][V];
printf("Enter the graph: \n");
for(int i=0;i<V;i++){
for(int j=0;j<V;j++){
scanf("%d",&g[i][j]);
}
}
warshallAlgo(g);
return 0;
}
