-
-
Save drnickallgood/6bc720ba69f27968835f88a45247d485 to your computer and use it in GitHub Desktop.
Floyd Warshall
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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,