الگوریتم فلوید

[رامین مرادی]

سلام دوستان این کدی که قرار دادم مربوط به پیاده سازی الگوریتم فلویده مال یکی از دوستامه من زیاد نتونستم بهش توضیح بدم اگه امکان داره این کد رو برام تشریح کنید البته اگه خط به خط باشه ممنون میشم.


#include <stdio.h>
#include <dos.h>
#include <conio.h>
#include <iostream.h>


void calcpdn(int n);
void showvs(int,int);

int c[4][4];
int p[4][4];
int d[4][4];

int main(void)
{
int n ;
struct time start,end;
clrscr();
printf("\nPlease Enter the n:");
scanf("%d",&n);
for (int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
printf("\nPlease Enter The P[%d,%d]:",i,j);
scanf("%d",&c[i][j]);
}
gettime(&start);
calcpdn(n);
gettime(&end);
int s,ms ;
if(end.ti_sec>start.ti_sec) s =end.ti_sec-start.ti_sec ;
else s = start.ti_sec-end.ti_sec ;
if(end.ti_hund>start.ti_hund) ms= end.ti_hund-start.ti_hund ;
else ms =start.ti_hund-end.ti_hund ;

printf("\n\n\nThe Differ Time %d:%d",
s,ms);
printf("\n\n\nFor Exit enter i=-1\n");
while (1)
{ printf("\n\nPlease Enter the raseh i =");
scanf("%d",&i);
printf("\n\nPlease Enter the raseh j =");
scanf("%d",&j);
if (i == -1) break ;

if (p[i][j] != -1 ){
printf("\n\naz %d =====>> %d kotahtarin masir gozar az rashyae zir mibashad : ",i,j);
showvs(i,j);
} else
printf("\n\naz %d =====>> %d kotahtrain masir masir mostaghim mibashad : ",i,j);
}



getch();
return 0;
}
void calcpdn (int n)
{
for(int i =0;i<n;i++)
for(int j=0;j<n;j++)
{
p[i][j] = -1;
d[i][j] = c[i][j] ;
}
for (int k=0 ; k<n ; k++)
for(i=0 ; i<n ; i++)
for(j=0;j<n;j++)
{delay(50);
int dk = d[i][k] + d[k][j] ;
if (d[i][j] > dk)
{
d[i][j] = dk ;
p[i][j] = k;
}
}
}
void showvs (int i ,int j)
{int k;
if (p[i][j] == -1) return ;
k =p[i][j] ;
showvs(i,k);
cout << k << "\t";
showvs(k,j);
}

[hadi0x7c7]

این کد از برنامه نویسی پویا استفاده میکنه بهتره کتابهای طراحی الگوریتم رو مطالعه کنید تا زود تر نتیجه بگیرید، ایده کلی اینطوره که میاد کوتاه ترین مسیر بین دو راس i و j رو حساب میکنه و هر بار یکی از رئوس رو به عنوان راس میانی قرار میده مثلا کوتاه ترین مسیر بین I و j و از راس 1 استفاده کنه و توی حلقه بعد از رئوس 1 و 2 استفاده کنه و ....