Pagini recente » Cod sursa (job #1199523) | kikis_delivery_service | Cod sursa (job #2680378) | Cod sursa (job #535395) | Cod sursa (job #600315)
Cod sursa(job #600315)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 1001
int * * royfloyd(int * * vertTab,int nrEdges);
int min(int a,int b);
int main()
{
FILE * fpin,* fpout;
fpin=fopen("royfloyd.in","r");
fpout=fopen("royfloyd.out","w");
int nrEdges;
fscanf(fpin,"%d",&nrEdges);
int i,j,* * vertTab;
vertTab=(int * *)calloc(nrEdges,sizeof(int *));
for (i=0;i<nrEdges;i++)
vertTab[i]=(int *)calloc(nrEdges,sizeof(int));
for (i=0;i<nrEdges;i++)
for (j=0;j<nrEdges;j++)
fscanf(fpin,"%d",&vertTab[i][j]);
fclose(fpin);
int * * shPathsTab=royfloyd(vertTab,nrEdges);
/*for (i=0;i<nrEdges;i++)
{
for (j=0;j<nrEdges;j++)
printf("%d ",shPathsTab[i][j]);
printf("\n");
}*/
for (i=0;i<nrEdges;i++)
{
for (j=0;j<nrEdges;j++)
fprintf(fpout,"%d ",shPathsTab[i][j]);
fprintf(fpout,"\n");
}
fclose(fpout);
return 0;
}
int * * royfloyd(int * * vertTab,int nrEdges)
{
int i,j,k,* * shPathsTab;
shPathsTab=(int * *)calloc(nrEdges,sizeof(int *));
for (i=0;i<nrEdges;i++)
shPathsTab[i]=(int *)calloc(nrEdges,sizeof(int));
for (i=0;i<nrEdges;i++)
for (j=0;j<nrEdges;j++)
if (i==j) shPathsTab[i][j]=0;
else if (vertTab[i][j]==0) shPathsTab[i][j]=INFINITY;
else shPathsTab[i][j]=vertTab[i][j];
for (k=0;k<nrEdges;k++)
for (i=0;i<nrEdges;i++)
for (j=0;j<nrEdges;j++)
shPathsTab[i][j]=min(shPathsTab[i][j],shPathsTab[i][k]+shPathsTab[k][j]);
return shPathsTab;
}
int min(int a,int b)
{
if (a<b) return a;
return b;
}