Skip to main content

Posts

Showing posts with the label Graph

Solve All-Pairs Shortest Path Problem using Floyd - Warshall Algorithm

#include<stdio.h> #include<conio.h> #define inf 999 void main() { int i,j,k,n,w[20][20]; printf("\n Enter the no. of vertices : "); scanf("%d",&n); printf("\n Enter the weights : "); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { printf("w[%d][%d]= ",i,j); scanf("%d",&w[i][j]); if(i!=j && (w[i][j]==0)) w[i][j]=inf; } for(i=1;i<=n;i++) { printf("\n"); for(j=1;j<=n;j++) printf("%d\t",w[i][j]); } for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(w[i][k]+w[k][j]<w[i][j]) w[i][j]=w[i][k]+w[k][j]; } } } printf("\n The resultant Matrix : \n"); for(i=1;i<=n;i++) { printf("\n"); for(j=1;j<=n;j++) printf("%d\t",w[i][j]); } getch(); } Output   Print   Output Enter the no. of vertices : 5 E