Algoritmul Roy Floyd

royfloyd.cpp

#include <stdio.h>
#define MAX 105
#define FIN "royfloyd.in"
#define FOUT "royfloyd.out"

//function prototypes
void read();
void RoyFloyd();
void write();

int n, mat[ MAX ][ MAX ];

int main() {

    read();
    RoyFloyd();
    write();

   return 0; 
};

void read() {

    int i,j;

    freopen(FIN , "r", stdin);

    scanf("%ld", &n);

    for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                scanf("%d", &mat[ i ][ j ]);

    fclose( stdin ); 
};

//Roy-Floyd in action using Dynamic Programming
void RoyFloyd() {

    int i,
        j,
        k;
             for(k = 1; k <= n; k++) 

                 for(i = 1; i <= n; i++) 

                    for(j = 1; j <= n; j++) 

                        if(i != j && mat[ i ][ k ] && mat[ k ][ j ]) 

                             if(mat[ i ][ k ] + mat[ k ][ j ] < mat[ i ][ j ] || !mat[ i ][ j ])

                                            mat[ i ][ j ] = mat[ i ][ k ] + mat[ k ][ j ];
};

void write() {

    int i,
        j;

    freopen(FOUT, "w", stdout);

             for(i = 1; i <= n; i++) {

                 for(j = 1; j <= n; j++) 
 
                     printf("%d ", mat[ i ][ j ]);

                 printf("\n");
             }

    fclose( stdout );

}