[최단 경로] 플로이드 워셜(Floyd-Warshall) 알고리즘

 

 

💡 플로이드 워셜 (Floyd-Warshall) 알고리즘

- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 알고리즘

- 그래프에 존재하는 모든 노드 쌍에 대한 최단 경로를 한번에 구할 수 있다.

- 노드의 갯수가 적을 경우에 사용한다.

- 2차원 리스트에 '최단 거리' 정보를 저장한다.

- 시간 복잡도 : $O(N^3)$

- 노드의 갯수가 N개일때, N번의 단계를 수행하며, 단계마다 $O(N^2)$의 연산을 통해 '현재 노드를 거쳐가는' 모든 경로를 고려한다.

 

 

💡 플로이드 워셜 알고리즘의 원리

- 각 단계에서는 '해당 노드를 거쳐가는 경우'를 고려한다.

예) 1번 노드에 대해서 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려한 루 최단 거리를 갱신한다.

A →  B 로 가는 비용이 3일 때, A → 1번 노드 →  B로 가는 비용이 2라는 것이 밝혀지면 A  → B로 가는 비용을 2로 하는 갱신하는 것이다.

 

따라서, 알고리즘에서는 현재 확인하고 있는 노드를 제외하고 N - 1개의 노드 중에서 서로 다른 노드 (A, B) 쌍을 선택한 후 비용을 확인한 후에 최단 거리를 갱신한다.

 

점화식은 다음과 같다.

\[ D_{ab} = \min(D_{ab},\; D_{ak} + D_{kb}) \]

 

전체적으로  3중 반복문을 이용하려 이 점화식에 따라 최단 거리 테이블을 갱신하면 된다.

 

 

Step 0 )

연결된 간선 = 해당 값을 채워 넣음

연결되지 않은 간선 = 무한 값

출발 / 도착	1	2	3	4
1	0	4	무한	6
2	3	0	7	무한
3	5	무한	0	4
4	무한	무한	2	0

 

 

Step 1)

1 번 노드를 거쳐 가는 경우를 고려한다.

\[ D_{23} = \min(D_{23},\; D_{21} + D_{13}) \]

\[ D_{24} = \min(D_{23},\; D_{21} + D_{14}) \]

\[ D_{32} = \min(D_{32},\; D_{31} + D_{12}) \]

\[ D_{34} = \min(D_{34},\; D_{31} + D_{14}) \]

\[ D_{42} = \min(D_{42},\; D_{41} + D_{12}) \]

\[ D_{43} = \min(D_{43},\; D_{41} + D_{13}) \]

 

이 6가지 경우만 하나씩 확인하며 값을 계산하여 갱신한다.

출발 / 도착	1	2	3	4
1	0	4	무한	6
2	3	0	7	9
3	5	9	0	4
4	무한	무한	2	0

 

해당 과정을 마지막 노드까지 반복하면 된다.

 

<결과>

출발 / 도착	1	2	3	4
1	0	4	8	6
2	3	0	7	9
3	5	9	0	4
4	7	11	2	0

 

 

---

 

 

💡 플로이드 워셜 알고리즘 구현

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

public class FloydWarshallPractice {

    static final int INF = (int) 1e9;
    static int n, m;
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        graph = new int[n + 1][n + 1];

        for(int i = 0; i <= n; i++){
            Arrays.fill(graph[i], INF);
        }

        for(int a = 1; a <= n; a++) {
            for(int b = 1; b <= n; b++) {
                if(a == b) graph[a][b] = 0;
            }
        }

        for(int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph[a][b] = c;

        }

        for(int k = 1; k <= n; k++) {
            for(int a = 1; a <= n; a++) {
                for(int b = 1; b <= n; b++) {
                    graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
                }
            }
        }

        for(int a = 1; a <= n; a++) {
            for(int b = 1; b <= n; b++) {
                if(graph[a][b] == INF) {
                    System.out.print("INFINITY");
                }else {
                    System.out.print(graph[a][b] + " ");
                }
            }
            System.out.println();
        }


    }
}

 

 

 

 

 

 

참고 ) 

https://product.kyobobook.co.kr/detail/S000001810273?utm_source=google&utm_medium=cpc&utm_campaign=googleSearch>_network=g>_keyword=>_target_id=aud-901091942354:dsa-608444978378>_campaign_id=9979905549>_adgroup_id=132556570510&gad_source=1

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고