import java.util.Arrays;

public class FloydWarshall {
	public static void main(String[] args) {
		// input example 1
		int[][] inputGraph1 = { { 0, 4, 6, 0, 0 }, { 0, 0, 1, 2, 4 }, { 0, 1, 0, 0, 2 }, { 2, 0, 0, 0, 0 },
				{ 0, 0, 0, 2, 0 } };
		// We choose Integer so we can use "null" as infinity 
		Integer[][] result1 = new Integer[inputGraph1.length][inputGraph1.length];

		System.out.println("There is no negative weight cycle: " + floydWarshall(inputGraph1, result1));
		for (int k = 0; k < result1.length; k++) {
			System.out.println(Arrays.toString(result1[k]));
		}
		// input example 2
		int[][] inputGraph2 = { 
				{ 0, 10, 0, 8, 0, 0 }, 
				{ -6, 0, 0, 2, 2, 0 }, 
				{ -10, -8, 0, -5, 0, 5 }, 
				{ 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 10, 8, 0, -2 },
				{ -7, 0, 0, 0, 0, 0 } };
		Integer[][] result2 = new Integer[inputGraph2.length][inputGraph2.length];
		System.out.println("There is no negatice weight cycle: " + floydWarshall(inputGraph2, result2));
		for (int k = 0; k < result2.length; k++) {
			System.out.println(Arrays.toString(result2[k]));
		}
		// input example 3
		int[][] inputGraph3 = { 
				{ 0, -10, 0, 8, 0, 0 }, 
				{ -6, 0, 0, 2, 2, 0 }, 
				{ -10, -8, 0, -5, 0, 5 }, 
				{ 0, 0, 0, 0, 0, 0 },
				{ 0, 0, 10, 8, 0, -2 },
				{ -7, 0, 0, 0, 0, 0 } };
		Integer[][] result3 = new Integer[inputGraph3.length][inputGraph3.length];
		boolean shouldBeFalse = floydWarshall(inputGraph3, result3);
		System.out.println("There is no negatice weight cycle: " + shouldBeFalse);
		if(shouldBeFalse) {
			for (int k = 0; k < result3.length; k++) {
				System.out.println(Arrays.toString(result3[k]));
			}
		}
	}

	public static boolean floydWarshall(int[][] input, Integer[][] result) {
		for (int i = 0; i < input.length; i++) {
			for (int j = 0; j < input.length; j++) {
				if (input[j][i] != 0) {
					result[j][i] = input[j][i];
				} else {
					result[j][i] = null;
				}
			}
		}
		
		for (int i = 0; i < input.length; i++) {
			for (int j = 0; j < input.length; j++) {
				for (int k = 0; k < input.length; k++) {
					//TODO
				}
				//TODO
			}

		}
		return true;
	}
}