플로이드-워셜 알고리즘

❓ 플로이드 워셜 알고리즘?
 : 가중 그래프에서 모든 정점 사이의 최단 경로(최소 비용)를 구하는 알고리즘

 ▪️ 플로이드 워셜 알고리즘은 O(n^3) 시간 복잡도를 갖는다.
 ▪️ 그래프에 음수 사이클이 없어야 한다.
 ▪️ 가중치가 음수 또는 양수이다.

 

참고로 그래프에서 최단 경로를 구하는 알고리즘에는

• 다익스트라 알고리즘
• 벨만-포드 알고리즘
• 플로이드-워셜 알고리즘

이 있다!

 

이번 포스트에서는 플로이드 워셜에 대해 알아보자.

 

---

 

플로이드 워셜 알고리즘은각 정점 사이의 최단 거리를 저장하는 일종의 dp 테이블을 가지고 문제를 해결한다!

dp[i][j]는 i정점에서 j정점으로 가는 최소 비용을 의미한다.

 

1️⃣ 처음 dp[i][j]에는 i에서 j로 바로 가는 비용이 저장된다. (바로 갈 수 없다면, 무한대로 초기화)

2️⃣ i와 j가 아닌 정점 k를 추가해, k를 경유해서 i에서 j로 가는 비용을 구한다. 구한 값과 기존 비용을 비교해 작은 값으로 dp 테이블을 업데이트한다.

dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j])

 

3️⃣ 이 과정을 k = 1부터 k = n 까지 반복한다. (n: 정점의 갯수)

 

구체적인 예시로 살펴보자!

 

 

최단경로 테이블을 초기화한다. i → j가 연결되어 있지 않다면 무한대로 초기화한다.

 

i에서 j를 갈 때, 정점 1을 경유해서 가는 방법을 고려해서 테이블을 업데이트 한다.

dp[i][j] = Math.min(dp[i][j], dp[i][1] + dp[1][j])

 

예를 들어 dp[2][4]의 경우 기존에는 INF였지만 1을 경유해서 가는 dp[2][1] + dp[1][4] = 9이기 때문에9로 업데이트가 된다.

 

i에서 j를 갈 때, 정점 2을 경유해서 가는 방법을 고려해서 테이블을 업데이트 한다.

dp[i][j] = Math.min(dp[i][j], dp[i][2] + dp[2][j])

 

같은 방식으로, 3을 경유해서 가는 방법을 고려해서 테이블을 업데이트한다.

이때, dp[i][j]는 단순히 i → 3 → j를 고려하는 것이 아니다! 처음에 이렇게 생각했다가 '아니 그럼 1 → 3 → 2 → 4가 최단 경로면 어딱하지?'라고 생각했었다!

그런데 사실은 step이 k일때, dp[i][j]는 1 ~ k를 경유지로 고려했을 때 i에서 j로 가는 최소 비용이다!

즉, 1에서 4로 가는데, 1~k를 경유지로 모든 경우를 고려했을 때의 최소 비용이다. (ex. k가 3일때 1 → 4, 1 → 2 → 4,  1 → 3 → 4, 1 → 2 → 3 → 4, 1 → 3 → 2 → 4를 모두 고려해본 결과이다.) 

같은 방식으로, 4를 경유해서 가는 방법을 고려해서 테이블을 업데이트한다.

 

플로이드-워셜의 핵심은 경유지의 경우를 1개에서 점차 늘려가면서 모든 경우를 확인하는 것이다.

말했듯이 일종의 DP알고리즘이다!

 

이제 코드를 작성해보자!

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

 

플로이드 워샬 알고리즘의 기본적인 문제이다.

n개의 정점이 있고, 그 정점을 잇는 간선이 m개 있을 때, 각 정점 사이의 최소 비용을 모두 구하는 문제이다! (간선 m에는 가중치가 적용되어 있다)

 

✍🏻 문제 풀이

import java.util.*;

public class Main {
  static final int MAX_VALUE = 100_000_001;
  static int[][] cost;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); // 정점의 갯수
    int m = sc.nextInt(); // 간선의 갯수
    cost = new int[n+1][n+1]; // cost[i][j]는 i -> j도시로 가는 최소 비용 (dp테이블)

    for(int i = 1; i <= n; ++i) { // cost[][] 초기화
      for(int j = 1; j <= n; ++j) {
        cost[i][j] = MAX_VALUE;
        if(i == j) cost[i][j] = 0;
      }
    }

    for(int i = 0; i < m; ++i) { // 입력값
      int from = sc.nextInt();
      int to = sc.nextInt();
      int fare = sc.nextInt();

      cost[from][to] = Math.min(cost[from][to], fare);
    }

    // 플로이드-워샬
    for(int k = 1; k <= n; ++k) {
      for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
          cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
        }
      }
    }

    for(int i = 1; i <= n; ++i) {
      for(int j = 1; j <= n; ++j) {
        System.out.print((cost[i][j] == MAX_VALUE)? "0 " : (cost[i][j] + " "));
      }
      System.out.println();
    }
  }
}