본문 바로가기
알고리즘 개념 & 유형정리/플로이드-워셜

플로이드 - 워셜 알고리즘 개념정리, 예시, 구현, 관련문제

by 뚱주 2026. 1. 11.
알고리즘 설명

 

플로이드 워셜 알고리즘은 최단경로를 찾는 알고리즘이다.

모든 노드에서 다른 노드로 가는 최단 거리를 찾을 수 있다. 그래서 2차원 배열을 생성하여 값을 저장해준다.

각 노드를 중간노드로 허용하면서 시작노드와 목적지노드의 최단경로를 갱신해나가는 알고리즘이다. 즉, 3중 반복문이므로 시간복잡도는 O^3 이다.

 

예시

 

 

그래프의 상태가 위와 같다고 가정하고 알고리즘을 실행한다. 위 그래프를 2차원 배열로 나타내면 아래와 같다.

 

단계 0

 

중간 노드로 0을 거쳐 갈 수 있다고 한다면 최단거리 갱신은 아래와 같이 이루어진다.

// 0을 중간노드로 거쳐가는 경우

dist[0][0] = Math.min(dist[0][0], dist[0][0] + dist[0][0]);     // (0, 0)
dist[0][1] = Math.min(dist[0][1], dist[0][0] + dist[0][1]);     // (0, 0+83)
dist[0][2] = Math.min(dist[0][2], dist[0][0] + dist[0][2]);     // (38, 0+38)
dist[0][3] = Math.min(dist[0][3], dist[0][0] + dist[0][3]);     // (7, 0+7)

dist[1][0] = Math.min(dist[1][0], dist[1][0] + dist[0][0]);     // (15, 15+0)
dist[1][1] = Math.min(dist[1][1], dist[1][0] + dist[0][1]);     // (0, 15+83)
dist[1][2] = Math.min(dist[1][2], dist[1][0] + dist[0][2]);     // (30, 15+38)
dist[1][3] = Math.min(dist[1][3], dist[1][0] + dist[0][3]);     // (83, 15+7): 갱신

dist[2][0] = Math.min(dist[2][0], dist[2][0] + dist[0][0]);     // (67, 67+0)
dist[2][1] = Math.min(dist[2][1], dist[2][0] + dist[0][1]);     // (99, 67+83)
dist[2][2] = Math.min(dist[2][2], dist[2][0] + dist[0][2]);     // (0, 67+38)
dist[2][3] = Math.min(dist[2][3], dist[2][0] + dist[0][3]);     // (44, 67+7)

dist[3][0] = Math.max(dist[3][0], dist[3][0] + dist[0][0]);     // (14, 14+0)
dist[3][1] = Math.min(dist[3][1], dist[3][0] + dist[0][1]);     // (46, 14+81)
dist[3][2] = Math.min(dist[3][2], dist[3][0] + dist[0][2]);     // (81, 14+38): 갱신
dist[3][3] = Math.min(dist[3][3], dist[3][0] + dist[0][3]);     // (0, 14+7)

 

dist[1][3]과 dist[3][2]의 값이 갱신된다. 갱신되는 의미 아래와 같다.

  • dist[1][3]: 노드1→노드3 으로 가는 것보다 노드1→노드0→노드3 으로 가는게 더 최단거리이다.
  • dist[3][2]: 노드3→노드2 으로 가는 것보다 노드3→노드0→노드2 으로 가는게 더 최단거리이다.

이후 상태는 아래와 같다.

단계 1

 

중간 노드로 1을 거쳐 갈 수 있다고 한다면 최단거리 갱신은 아래와 같이 이루어진다.

 

// 1을 중간노드로 거쳐가는 경우

dist[0][0] = Math.min(dist[0][0], dist[0][1] + dist[1][0]);     // (0, 83+15)
dist[0][1] = Math.min(dist[0][1], dist[0][1] + dist[1][1]);     // (83, 83+0)
dist[0][2] = Math.min(dist[0][2], dist[0][1] + dist[1][2]);     // (38, 83+30)
dist[0][3] = Math.min(dist[0][3], dist[0][1] + dist[1][3]);     // (7, 83+22(1->0->3))

dist[1][0] = Math.min(dist[1][0], dist[1][1] + dist[1][0]);     // (15, 0+15)
dist[1][1] = Math.min(dist[1][1], dist[1][1] + dist[1][1]);     // (0, 0+0)
dist[1][2] = Math.min(dist[1][2], dist[1][1] + dist[1][2]);     // (30, 0+30)
dist[1][3] = Math.min(dist[1][3], dist[1][1] + dist[1][3]);     // (22, 0+22)

dist[2][0] = Math.min(dist[2][0], dist[2][1] + dist[1][0]);     // (67, 99+15)
dist[2][1] = Math.min(dist[2][1], dist[2][1] + dist[1][1]);     // (99, 99+0)
dist[2][2] = Math.min(dist[2][2], dist[2][1] + dist[1][2]);     // (0, 99+30)
dist[2][3] = Math.min(dist[2][3], dist[2][1] + dist[1][3]);     // (44, 99+22)

dist[3][0] = Math.min(dist[3][0], dist[3][1] + dist[1][0]);     // (14, 46+15)
dist[3][1] = Math.min(dist[3][1], dist[3][1] + dist[1][1]);     // (46, 46+0)
dist[3][2] = Math.min(dist[3][2], dist[3][1] + dist[1][2]);     // (52, 46+30)
dist[3][3] = Math.min(dist[3][3], dist[3][1] + dist[1][3]);     // (0, 46+22)

 

이 단계에서는 최단거리가 갱신되지 않는다.

 

이후 상태는 아래와 같다.

단계 2

 

중간 노드로 2를 거쳐 갈 수 있다고 한다면 최단거리 갱신은 아래와 같이 이루어진다.

 

// 2를 중간노드로 거쳐가는 경우

dist[0][0] = Math.min(dist[0][0], dist[0][2] + dist[2][0]);     // (0, 38+67)
dist[0][1] = Math.min(dist[0][1], dist[0][2] + dist[2][1]);     // (83, 38+99)
dist[0][2] = Math.min(dist[0][2], dist[0][2] + dist[2][2]);     // (38, 38+0)
dist[0][3] = Math.min(dist[0][3], dist[0][2] + dist[2][3]);     // (7, 38+44)

dist[1][0] = Math.min(dist[1][0], dist[1][2] + dist[2][0]);     // (15, 30+67)
dist[1][1] = Math.min(dist[1][1], dist[1][2] + dist[2][1]);     // (0, 30+99)
dist[1][2] = Math.min(dist[1][2], dist[1][2] + dist[2][2]);     // (30, 30+0)
dist[1][3] = Math.min(dist[1][3], dist[1][2] + dist[2][3]);     // (22, 30+44)

dist[2][0] = Math.min(dist[2][0], dist[2][2] + dist[2][0]);     // (67, 0+67)
dist[2][1] = Math.min(dist[2][1], dist[2][2] + dist[2][1]);     // (99, 0+99)
dist[2][2] = Math.min(dist[2][2], dist[2][2] + dist[2][2]);     // (0, 0+0)
dist[2][3] = Math.min(dist[2][3], dist[2][2] + dist[2][3]);     // (44, 0+44)

dist[3][0] = Math.min(dist[3][0], dist[3][2] + dist[2][0]);     // (14, 52+67)
dist[3][1] = Math.min(dist[3][1], dist[3][2] + dist[2][1]);     // (46, 52(3->0->2)+99)
dist[3][2] = Math.min(dist[3][2], dist[3][2] + dist[2][2]);     // (52, 52+0)
dist[3][3] = Math.min(dist[3][3], dist[3][2] + dist[2][3]);     // (0, 52+44)

 

이 단계에서는 최단거리가 갱신되지 않는다.

 

이후 상태는 아래와 같다.

 

단계 3

 

중간 노드로 3을 거쳐 갈 수 있다고 한다면 최단거리 갱신은 아래와 같이 이루어진다.

 

// 3을 중간노드로 거쳐가는 경우

dist[0][0] = Math.min(dist[0][0], dist[0][3] + dist[3][0]);     // (0, 7+14)
dist[0][1] = Math.min(dist[0][1], dist[0][3] + dist[3][1]);     // (83, 7+46): 갱신
dist[0][2] = Math.min(dist[0][2], dist[0][3] + dist[3][2]);     // (38, 7+52)
dist[0][3] = Math.min(dist[0][3], dist[0][3] + dist[3][3]);     // (7, 7+0)

dist[1][0] = Math.min(dist[1][0], dist[1][3] + dist[3][0]);     // (15, 22+14)
dist[1][1] = Math.min(dist[1][1], dist[1][3] + dist[3][1]);     // (0, 22+46)
dist[1][2] = Math.min(dist[1][2], dist[1][3] + dist[3][2]);     // (30, 22+52)
dist[1][3] = Math.min(dist[1][3], dist[1][3] + dist[3][3]);     // (22, 22+0)

dist[2][0] = Math.min(dist[2][0], dist[2][3] + dist[3][0]);     // (67, 44+14): 갱신
dist[2][1] = Math.min(dist[2][1], dist[2][3] + dist[3][1]);     // (99, 44+46): 갱신
dist[2][2] = Math.min(dist[2][2], dist[2][3] + dist[3][2]);     // (0, 44+52)
dist[2][3] = Math.min(dist[2][3], dist[2][3] + dist[3][3]);     // (44, 44+0)

dist[3][0] = Math.min(dist[3][0], dist[3][3] + dist[3][0]);     // (14, 0+14)
dist[3][1] = Math.min(dist[3][1], dist[3][3] + dist[3][1]);     // (46, 0+46)
dist[3][2] = Math.min(dist[3][2], dist[3][3] + dist[3][2]);     // (52, 0+52)
dist[3][3] = Math.min(dist[3][3], dist[3][3] + dist[3][3]);     // (0, 0+0)

 

dist[0][1], dist[2][0], dist[2][1]의 값이 갱신된다. 갱신되는 의미 아래와 같다.

  • dist[0][1]: 노드0→노드1 으로 가는 것보다 노드0→노드3→노드1 으로 가는 게 더 최단거리이다.
  • dist[2][0]: 노드2→노드0 으로 가는 것보다 노드2→노드3→노드0 으로 가는 게 더 최단거리이다.
  • dist[2][1]: 노드2→노드1 으로 가는 것보다 노드2→노드3→노드1 으로 가는 게 더 최단거리이다.

 

이후 상태는 아래와 같다.

 

이해하기 어려웠던 부분

 

  1. 시작 노드에서 목적지 노드 까지 도달하는데 모든 경로를 고려하는가?
    • 알고리즘을 눈으로만 따라가다 보면 1개의 지점만 거쳐가는 경우만 고려하여 최단경로를 구하는 것 같이 보였다.
      즉, 노드0에서 노드2로 가는 최단 경로를 구하기 위해 0 → 1 → 3 → 2 경로도 고려를 하는가?에 대해 궁금했다.

      정리하자면, 알고리즘 내에서는 0 → 3 → 2 경로를 고려할 때, 0 → 3으로 가는 경로 안에 이미 0 → 1 → 3 경로를 고려한 최단 거리가 담겨있다.

      위 예시로 설명을 하자면 0을 중간노드로 거쳐가는 단계에서 dist[3][2]가 갱신되었다. 즉, dist[3][2]에는 노드3 → 노드0 → 노드2 경로를 고려한 최단 거리가 담겨있다.

      이후, 2를 중간노드로 거쳐가는 단계에서 dist[3][1]를 구하고자 할 때, dist[3][2] + dist[2][1]로 계산하여 최소값으로 dist[3][1]을 갱신한다.
      이때, dist[3][2] 값에는 노드3 → 노드0 → 노드2를 경로를 고려한 최단거리가 담겨있기 때문에 dist[3][2] + dist[2][1]는dist[3][2]( = dist[3][0] + dist[0][2] ) + dist[2][1]로 3 → 0 → 2 → 1 경로를 고려하게 된다.

  2. 왜 중간에 거쳐가는 노드(k)가 가장 바깥 반복문에 있어야 하는가?
    • k가 2라는 의미는 0~2번 노드를 중간노드로 허용했을때의 최단거리이다. 즉, k가 3을 거쳐갔을 경우는 포함되지 않는다.

      만약, k가 반복문의 안에 있다면, 중간노드로 모든 노드를 허용하게 된다. 즉, 최단거리가 아닌 경로를 참조하게 되어 알고리즘이 깨진다.

      정리하면, 플로이드-워셜 알고리즘에서는 이전 단계(k-1)의 결과만 사용해야 하므로 k를 가장 바깥 반복문으로 써주어야 한다.
구현
import java.io.*;
import java.util.*;


public class Solution_for_11404 {
    static int N, M;
    static int[][] maps;

    static int INF = 9_900_001;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        maps = new int[N][N];

        // 인접행렬을 INF로 초기화 함(시작노드와 목적지노드가 동일한 경우 0)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i != j) {
                    maps[i][j] = INF;
                }
            }
        }
        
        // 간선을 이어줌
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());

            int startNode = Integer.parseInt(st.nextToken()) - 1;
            int endNode = Integer.parseInt(st.nextToken()) - 1;
            int cost = Integer.parseInt(st.nextToken());

            // 문제에서 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."
            if (maps[startNode][endNode] < cost) continue;

            maps[startNode][endNode] = cost;
        }

        floyd();

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

    public static void floyd() {
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    maps[i][j] = Math.min(maps[i][j], maps[i][k] + maps[k][j]);
                }
            }
        }
    }
}
관련문제
플랫폼 링크 요약 풀이 복습
백준 https://www.acmicpc.net/problem/11404 기본문제, INF 범위(Integer.MAX_VALUE로 하면 안되는 이유) https://sen-zoo.tistory.com/39  
백준 https://www.acmicpc.net/problem/17182 시작노드에서 목적지노드까지의 최단거리가 아닌 모든 노드를 탐색하는 최단거리 구하는 문제 https://sen-zoo.tistory.com/40  
백준 https://www.acmicpc.net/problem/1719 일반적인 플로이드-워셜 문제에서 비용을 구하는 문제가 아닌 '경로'(다음에 방문할 노드)를 구하는 문제 https://sen-zoo.tistory.com/41 필요

 

'알고리즘 개념 & 유형정리 > 플로이드-워셜' 카테고리의 다른 글

[백준 1719] 택배  (0) 2026.01.13
[백준 17182] 우주 탐사선  (1) 2026.01.11
[백준 11404] 플로이드  (0) 2026.01.11

관련글

티스토리툴바