Floyd Warshall

h6.c

#include <stdio.h>
#include <stdlib.h>

void printMatrix(int matrix[4][4], int size) {
	int i = 0;
	int j = 0;

	for(i = 0; i <size; i++) {
		for(j = 0; j <size; j++) {
			printf("%d, ", matrix[i][j]);
		}
		
		printf("\n");
	}
}

void floydWarshall(int orig[4][4], int new[4][4], int size) {
	// Zero-indexing
	int i, j, k = 0;
	int n = 4;			// N has 4 elements
	int res1, res2 = 0;

	for(k = 0; k < n; k++) {
		for(i = 0; i < n; i++) {
			for(j =0; j <n; j++) {
			
				//res 1 i 
				res1 = orig[i][j];
				res2 = orig[i][k] + orig[k][j];

				if(res1 <= res2) {
					new[i][j] = res1;
				}
				else {
					new[i][j] = res2;	
				}
			}
		}
	}
}

void modFloydWarshall(int orig[4][4], int new[4][4], int size) {

	// Zero-indexing
	int i, j, k = 0;
	int n = 4;			// N has 4 elements
	int res1, res2 = 0;

	
		for(i = 0; i < n; i++) {
			k = 0;
			for(j =0; j < n; j++) {
				//res 1 i 
				res1 = orig[i][j];
				res2 = orig[i][k] + orig[k][j];
				k++;
				if(res1 < res2) {
					new[i][j] = res1;
				}
				else {
					new[i][j] = res2;	
				}
			}
		}
}

int main(void) {

	// Reflexive, non-transitive matrix
	// Zero-indexing
	int t0[4][4] = {	{1, 1, 0, 0},
						{0, 1, 1, 0},
						{0, 0, 1, 1},
						{0, 0, 0, 1} };


	// This will be the new matrix to be built
	int t1[4][4] = { 	{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0}	};

	int t2[4][4] =	{	{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0}	}; 

	int t3[4][4] =	{	{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0}	}; 

	int t4[4][4] =	{	{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0}	};
 
	// Zero-indexing
	int i, j, k = 0;
	int n = 4;			// N has 4 elements
	int res1, res2 = 0;

	printf("----t0----\n");
	printMatrix(t0, 4);
	printf("\n");
	
	printf("\nFloyd Warshall\n");
	floydWarshall(t0, t1, n);
	printf("\n");
	printf("----t1----\n");
	printMatrix(t1, n);
	//printf("\n");
	
	floydWarshall(t1, t2, n);
	printf("\n");
	printf("----t2----\n");
	printMatrix(t2, n);
	//printf("\n");

	floydWarshall(t2, t3, n);
	printf("\n");
	printf("----t3----\n");
	printMatrix(t3, n);
	//printf("\n");
	
	floydWarshall(t3, t4, n);
	printf("\n");
	printf("----t4----\n");
	printMatrix(t4, n);
	//printf("\n");

	// Modified
	// This will be the new matrix to be built
	int mt1[4][4] = { 	{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0}	};

	int mt2[4][4] =	{	{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0}	}; 

	int mt3[4][4] =	{	{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0}	}; 

	int mt4[4][4] =	{	{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0},
						{0, 0, 0, 0}	};
 
 
	
	printf("\n\nModified Floyd Warshall\n\n");
	printf("----t0----\n");
	printMatrix(t0, 4);
	printf("\n");
	
	modFloydWarshall(t0, mt1, n);
	printf("\n");
	printf("----mt1----\n");
	printMatrix(mt1, n);
	
	modFloydWarshall(mt1, mt2, n);
	printf("\n");
	printf("----mt2----\n");
	printMatrix(mt2, n);

	modFloydWarshall(mt2, mt3, n);
	printf("\n");
	printf("----mt3----\n");
	printMatrix(mt3, n);

	modFloydWarshall(mt3, mt4, n);
	printf("\n");
	printf("----mt4----\n");
	printMatrix(mt4, n);

	return 0;

}

Result:

----t0----
1, 1, 0, 0,
0, 1, 1, 0,
0, 0, 1, 1,
0, 0, 0, 1,

Floyd Warshall

----t1----
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 1, 1,
0, 0, 0, 1,

----t2----
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 1, 1,
0, 0, 0, 1,

----t3----
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 1, 1,
0, 0, 0, 1,

----t4----
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 1, 1,
0, 0, 0, 1,

Modified Floyd Warshall

----t0----
1, 1, 0, 0,
0, 1, 1, 0,
0, 0, 1, 1,
0, 0, 0, 1,

----mt1----
1, 1, 0, 0,
0, 1, 1, 0,
0, 0, 1, 1,
0, 0, 0, 1,

----mt2----
1, 1, 0, 0,
0, 1, 1, 0,
0, 0, 1, 1,
0, 0, 0, 1,

----mt3----
1, 1, 0, 0,
0, 1, 1, 0,
0, 0, 1, 1,
0, 0, 0, 1,

----mt4----
1, 1, 0, 0,
0, 1, 1, 0,
0, 0, 1, 1,
0, 0, 0, 1,