플로이드-워셜

플로이드-워셜 알고리즘

---

• 최단 거리를 구하는 알고리즘입니다.
• 모든 노드 간의 최단 거리를 탐색 - 매우 중요, 출발 노드가 따로 정해진 것이 없습니다.

 

특징

---

• 음수 가중치가 있어도 수행할 수 있습니다.
• 동적 계획법의 원리를 사용합니다.
• O(NNN) - 노드의 세제곱, 꽤 느립니다.

 

핵심 이론

---

• 전체의 최단 경로는, 각 부분의 최단 경로가 합쳐져서 만들어집니다.

점화식 참고 사진

• 플로이드 워셜 점화식
  • D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

밑 설명 참고

1. 리스트를 선언하고 초기화 해줍니다.
2. 최단 거리 리스트에 그래프 데이터를 저장합니다.
3. 점화식으로 리스트 업데이트합니다.(3중 for 문) 
4. for 경유지 K에 관해(1~N): for 출발 노드 S에 관해(1~N): for 도착 노드 E에 관해(1~N): D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

---

백준 11404번 - 플로이드

 

문제

해당 문제를 보시게 되면, 도시의 입력 범위가 (2<= n <= 100)으로, 매우 작습니다. 또한, 출발 도시와 도착 도시가 정해지지 않았고, 모든 도시의 최솟값 쌍을 구하는 문제입니다. 따라서, 플로이드-워셜 알고리즘을 적용해볼 수 있습니다.

 

 

import java.util.Scanner;

public class Main {

    private static final int MAX_NUMBER = Integer.MAX_VALUE;

    private static long[][] city;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();
        int m = input.nextInt();

        //세팅
        city = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    city[i][j] = 0;
                } else {
                    city[i][j] = MAX_NUMBER;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int start = input.nextInt() - 1;
            int end = input.nextInt() - 1;
            int weight = input.nextInt();
            city[start][end] = Math.min(city[start][end], weight);
        }

        //플로이드-워셜 알고리즘
        for (int k = 0; k < n; k++) {
            for (int s = 0; s < n; s++) {
                for (int e = 0; e < n; e++) {
                    city[s][e] = Math.min(city[s][e], city[s][k] + city[k][e]);
                }
            }
        }

        //출력
        for(long[] nums : city) {
            for(long num : nums) {
                if(num == MAX_NUMBER) {
                    System.out.print(0 + " ");
                } else {
                    System.out.print(num + " ");
                }
            }
            System.out.println();
        }
    }
}

 

틀린 부분이 있다면 댓글 남겨주세요!