플로이드-워셜 기본 구현

public class Main {
    public static int INF = 1_000_000_000;

    public static void floydWarshall(int v, int e, int[][] data, int start) {
        int[][] dist = new int[v + 1][v + 1];

        for (int i = 1; i < v + 1; i++) {
            for (int j = 1; j < v + 1; j++) {
                if (i != j) {
                    dist[i][j] = INF;
                }
            }
        }

        for (int i = 0; i < data.length; i++) {
            dist[data[i][0]][data[i][1]] = data[i][2];
        }

        /**
         * 틀린 코드 주의 -> 경유지 k에 대해서 k가 가장 안쪽 루프에 위치하면, i와 j에 대해 이미 선택된 경로가 경유지를 거치지 않고 직접 경로로 결정될 수 있음
         */
//        for (int i = 1; i < v + 1; i++) {
//            for (int j = 1; j < v + 1; j++) {
//                for (int k = 1; k < v + 1; k++) {
//                    if (dist[i][j] != INF && dist[j][k] != INF) {
//                        dist[i][k] = Math.min(dist[i][k], dist[i][j] + dist[j][k]);
//                    }
//                }
//            }
//        }

        // 경유지 k를 거치는 경우에 대해서 봐야함 주의
        for (int k = 1; k < v + 1; k++) {
            // i -> j (k를 거쳐서 가는 경우가 짧을 때 업데이트)
            for (int i = 1; i < v + 1; i++) {
                for (int j = 1; j < v + 1; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        for (int i = 1; i < dist.length; i++) {
            for (int j = 1; j < dist[1].length; j++) {
                if (dist[i][j] == INF) {
                    System.out.printf("%5s", "INF");
                } else {
                    System.out.printf("%5d", dist[i][j]);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // Test code
        int[][] data = {{1, 2, 8}, {1, 3, 6}, {1, 5, 5}, {2, 3, -5}, {2, 4, 1}, {2, 6, 4}, {3, 4, 4}, {4, 7, 3}, {5, 6, 5}, {6, 2, 0}, {6, 7, -7}};
        floydWarshall(7, 11, data, 1);
        System.out.println();

        data = new int[][]{{1, 2, 8}, {1, 3, 6}, {1, 5, 5}, {2, 3, -5}, {2, 4, 1}, {2, 6, 4}, {3, 4, 4}, {4, 7, 3}, {5, 6, 5}, {6, 2, -5}, {6, 7, -7}};
        floydWarshall(7, 11, data, 1);
    }
}