[알고리즘] 플로이드 와샬 알고리즘 - 자바

📖 문제

플로이드 와샬 알고리즘을 직접 만들어보시오

📃 코드

public class Main {
    static int INF = 1000000;

    public static void main(String[] args) {

        int[][] dp = {
                { 0, 8, 1, INF },
                { INF, 0, INF, 1 },
                { INF, 2, 0, 9 },
                { 4, INF, INF, 0 }
        };

        DP(dp);
    }

    private static void DP(int[][] dp) {
        // result array
        int result[][] = new int[4][4];
        // init
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                result[i][j] = dp[i][j];
            }
        }

        // k = pass Node
        for (int k = 0; k < 4; k++) {
            // i = start Node
            for (int i = 0; i < 4; i++) {
                // j = end Node
                for (int j = 0; j < 4; j++) {
                    // start-pass-end < start-end -> change result
                    if (result[i][k] + result[k][j] < result[i][j]) {
                        result[i][j] = result[i][k] + result[k][j];
                    }
                }
            }
        }

        // print
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }
}

📑 결과