[JAVA] 백준 11404- 플로이드(플로이드-외샬 알고리즘이란?)

www.acmicpc.net/problem/11404

11404번: 플로이드

 

-플로이드-외샬 알고리즘

" 모든 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘" 

 

 

-원리

정점 i 에서 정점 j 까지 거리 = X

정점 i 에서 정점 k까지 거리 = Y

정점 k에서 정점 j 까지 거리 = Z

 

라고 할때, X = min ( Y+Z , X ) 를 정의한 것이 플루이드-외샬 알고리즘이다.

 

-구현

문제를 바탕으로 구현해보자.

 

정점이 1번 부터 5번까지 있다고 가정하자. 

 

"원리"에서 예시로 들었던 K를 먼저 기준으로 생각하면 된다.

 

k=1 일 때 ( = 거쳐야할 정점이 1번 정점일때)

i = 1 , j=1 

- 1번 정점에서 시작해서 1번 정점으로 가는 거리 = min ( 1번 정점에서 시작해서 1번 정점으로 가는 거리 , 1번 정점에서 시작해서 1번 정점으로 가는 거리 + 1번 정점에서 시작해서 1번 정점으로 가는 거리)

i = 1 , j=2

- 1번 정점에서 시작해서 2번 정점으로 가는 거리 = min ( 1번 정점에서 시작해서 1번 정점으로 가는 거리 ,1번 정점에서 시작해서 1번 정점으로 가는 거리  +1번 정점에서 시작해서 2번 정점으로 가는 거리)

 

 

...

 

 

i=3, j=4

- 3번 정점에서 시작해서 4번 정점으로 가는 거리 = min ( 3번 정점에서 시작해서 4번 정점으로 가는 거리 ,3번 정점에서 시작해서 1번 정점으로 가는 거리+1번 정점에서 시작해서 4번 정점으로 가는 거리)

 

 

...

 

 

k=2 일때도 마찬가지로 구현

 

---

 

최종 코드

 

import java.util.Scanner;

public class Main {

    static int n;
    static int m;
    static int INF = 100000*100 + 1;
    static int[][] dp = new int[101][101];


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]= INF;
            }
        }

        for(int i=0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int val = sc.nextInt();
            dp[a][b] = Math.min(dp[a][b],val);
        }

        for(int k = 1;k<=n;k++){
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=n;j++){
                    if(i!=j && dp[i][k]!=INF && dp[k][j]!=INF){
                        dp[i][j] = Math.min(dp[i][j] , dp[i][k] + dp[k][j]);
                    }
                }
            }
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dp[i][j] == INF) {
                    System.out.print(0 + " ");
                }
                else{
                    System.out.print(dp[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}

 

 

 

INF 는 최대한 크게 설정할 것.