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

플로이드 워셜 알고리즘이란?

플로이드-워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 모두 구하는 알고리즘이다. 따라서 2차원 테이블에 최단 거리 정보를 저장한다. 

	다익스트라	벨만-포드	플로이드-워셜
경로계산방식	One-To-All	One-to-One	All-to-All
음의 가중치	X	O	O
음수 사이클	X	X	X
최단거리테이블	1차원테이블	1차원테이블	2차원테이블
다른 알고리즘 포함	그리디	-	DP

 

경로 계산 방식에는 아래와 같은 종류가 있다. 

1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 ->벨만-포드 알고리즘  
2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 ->다익스트라 알고리즘
3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 ->플로이드-워셜 알고리즘

 

 

구현 방법

플로이드 워셜 알고리즘의 점화식

3중 반복문을 이용해 위 점화식을 기준으로 테이블을 갱신시킨다.

• a에서 b로 가는 최소 비용과 a에서 k를 거쳐 b로 가는 비용을 비교해 더 작은 값으로 갱신
• 매 단계마다 현재 노드를 거쳐 가는 노드를 기준으로 알고리즘을 수행
• 초기 테이블 설정 시 연결되지 않은 간선에는 INF를 넣고, 자기 자신으로 가는 비용은 모두 0으로 초기화.
• 시간 복잡도는 O(N^3)
  • 노드의 개수가 N개 일 때, N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는 모든 경로'를 고려한다. 따라서 시간 복잡도는 총 O(N^3)이다.

 

예시

[step 0] 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다. 연결되어 있는 간선에는 가중치 비용을, 연결되지 않은 간선에는 INF를 넣는다. 자기 자신으로 가는 비용은 모두 0으로 초기화한다. 

 

[step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

 

[step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

 

[step ~] 3번, 4번, ... 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

 

 

코드

import java.util.Arrays;
import java.util.Scanner;

public class FloydWarshall {
    final static int INF = Integer.MAX_VALUE; // 무한대를 나타내기 위해 Integer.MAX_VALUE 사용

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

        // 노드의 개수(n)과 간선의 개수(m)을 입력받음
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 그래프를 무한대로 초기화하고, 자기 자신으로 가는 비용은 0으로 초기화
        int[][] graph = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0; // 자기 자신으로 가는 비용은 0
        }

        // 간선 정보를 입력받아 그래프를 업데이트
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            graph[a][b] = c; // a에서 b로 가는 비용은 c
        }

        // 플로이드 워셜 알고리즘을 이용하여 모든 노드 쌍의 최단 경로를 계산
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][k] != INF && graph[k][j] != INF) { // 오버플로우 방지
                        graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                    }
                }
            }
        }

        // 결과 출력
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] == INF)
                    System.out.print("INFINITY ");
                else
                    System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }

        scanner.close();
    }
}

 

예시 문제

https://www.acmicpc.net/problem/11404

import java.util.*;
import java.io.*;

public class _11404 {
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int V=Integer.parseInt(br.readLine());
        int E=Integer.parseInt(br.readLine());
        int[][] distArr=new int[V+1][V+1];
        int INF= Integer.MAX_VALUE;
        for(int i=0;i<=V;i++){
            for(int j=0;j<=V;j++){
                if(i==j)
                    distArr[i][j]=0;
                else distArr[i][j]=INF;
            }
        }

        for(int i=0;i<E;i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int start=Integer.parseInt(st.nextToken());
            int end=Integer.parseInt(st.nextToken());
            int distance=Integer.parseInt(st.nextToken());
            distArr[start][end]=Math.min(distance, distArr[start][end]);
        }

        for(int k=0;k<=V;k++){
            for(int i=0;i<=V;i++){
                for(int j=0;j<=V;j++){
                    if(distArr[i][k]!=INF&&distArr[k][j]!=INF)
                        distArr[i][j]=Math.min(distArr[i][j], distArr[i][k]+distArr[k][j]);
                }
            }
        }

        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=1;i<=V;i++){
            for(int j=1;j<=V;j++){
                if(distArr[i][j]==INF)
                    bw.write("0 ");
                else
                    bw.write(distArr[i][j]+" ");
            }
            bw.write("\n");
            bw.flush();
        }

        bw.close();
    }
}