[ 그래프 ] 플로이드-워셜(백준 11404)

 플로이드-워셜

그래프에서 최단 거리를 구하는 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜)

• 모든 노드 간에 최단 경로 탐색 -> 시작 노드가 따로 정해져있지 않다.
• 음수 가중치 에지가 있어도 수행 가능하다. 다만, 사이클이 있으면 안된다.
• 동적 계획법의 원리를 이용해 알고리즘에 접근한다.
• 시간 복잡도는 O(V³)   노드가 1000개이면 시간초과가 일어날 확률이 높다.
  

💡  플로이드-워셜 핵심 이론

A노드에서 B노드까지 최단 경로를 구했다고 가졍했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로

 

🔍 도출한 플로이드-워셜 점화식

     D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

 

1. 리스트를 선언하고 초기화하기

D[S][E]는 노드 S에서 E까지의 최단 거리를 저장하는 리스트이다.

S==E 인 부분은 0(자신이 자신에게 가는), 나머지는 무한대로 채운다.

 

2. 최단 거리 리스트에 그래프 데이터 저장하기

D[S][E] = W(가중치) 데이터 저장

 

 

3. 점화식으로 리스트 업데이트

플로이드-워셜 알고리즘 로직
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 : 플로이드

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

 

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

입력	출력
5 14 1 2 2 1 3 3 1 3 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 3 5 10 3 1 8 1 4 2 5 1 7 3 4 2 5 2 4	0 2 3 1 4 12 0 15 2 5 8 5 0 1 1 10 7 13 0 3 7 4 10 6 0

 

문제 풀이

• 그냥 진짜 공식대로만 작성하면 풀림,,!!

 

실행 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P11404_FloydWarchall {
    static int[][] D;
    static int N, M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int INF = 99999999;
        N = Integer.parseInt(br.readLine()); //도시의 갯수(노드)
        M = Integer.parseInt(br.readLine()); //버스의 갯수(간선)
        D = new int[N+1][N+1]; //최단거리를 저장할 배열

        //자신이 자신에게 가는 루트는 0 넣기
        for(int i = 1; i <= N; i++) {
            Arrays.fill(D[i], INF);
            D[i][i] = 0;
        }

        // 버스 노선 저장
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); //시작
            int e = Integer.parseInt(st.nextToken()); //도착
            int m = Integer.parseInt(st.nextToken()); //비용
            D[s][e] = Math.min(D[s][e], m); // 기존 값과 비교하여 최소값 저장
        }

        //플로이드 워셜
        FloydWarchall();

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

    }

    private static void FloydWarchall() {
        for(int K=1; K<=N; K++){ //경유지
            for(int S=1; S<=N; S++){ //출발
                for(int E=1; E<=N; E++){ //도착
                    //지금 현재 S->E보다 S->K + K->E 값이 더 작으면 업데이트
                    D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);
                }
            }
        }
    }
}