Graph 최단거리 알고리즘 (3) 플로이드 워셜

N to N ( N<=500)

출발지와 도착지 모두 N개일때 쓰는 알고리즘

시간복잡도가 O(N^3)이므로 N이 적을때만 사용 가능하다.

 

i지점에서 j 지점까지 갈때의 최단거리가

k 지점을 거쳐서 가면 어느것이 더 최단거리일까? 라는것을 구해주면 된다.

 

 

샘플 코드

    
    static int[] d;
    static int N;
    static ArrayList<Node>[] adj = new ArrayList[N+1];
    static void floyd() {
        //1. d배열 INF 채우기
        Arrays.fill(d, INF);

        //2. 입력값으로 들어오는 간선 cost 받기 adj

        for (int k = 1; k <= N; k++) { //경유지가 밖에 있어야함.-> 대상이 되는 경유지를 고정 해야함.
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }