one-file-projects/floyd_warshall.c

47 lines
934 B
C
Raw Permalink Normal View History

2016-02-21 16:52:20 +01:00
#include <stdio.h>
2016-02-23 12:14:24 +01:00
#define N 5
2016-02-21 16:52:20 +01:00
typedef int Mat[N*N];
void matiter(Mat C, int (*reduce)(int old, int ik, int kj)) {
for(unsigned int k = 0; k < N; k++) {
for(unsigned int i = 0; i < N; i++) {
for(unsigned int j = 0; j < N; j++) {
C[i*N+j] = reduce(C[i*N+j], C[i*N+k], C[k*N+j]);
}
}
}
}
int floyd(int old, int ik, int kj) {
int new = ik + kj;
return ( old < new ? old : new );
}
int warshall(int old, int ik, int kj) {
return (old ? old : ik && kj);
}
int main( int argc, char *argv[] ) {
Mat C =
{
2016-02-23 12:14:24 +01:00
0 , 1 , 0 , 0 , 0,
0 , 0 , 1 , 0 , 0,
0 , 0 , 0 , 0 , 0,
1 , 0 , 0 , 0 , 0,
0 , 0 , 0 , 1 , 0,
2016-02-21 16:52:20 +01:00
};
matiter(C, *warshall);
for(unsigned int i = 0; i < N; i++) {
for(unsigned int j = 0; j < N; j++) {
printf("%5d ", C[i*N+j]);
}
printf("\n");
}
return 0;
}