플로이드-와샬(Floyd-Warshall) 알고리즘

1. 개념 🐕‍🦺

  플로이드-와샬(Floyd-Warshall) 알고리즘이란 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 다익스트라(Dijkstra) 알고리즘과 다르게 음의 가중치를 허용한다는 게 특징이라고 할 수 있다.

  다익스트라 알고리즘을 간단하게 설명하자면 출발 정점으로부터 모든 정점까지의 최단경로를 구하는 알고리즘이다. 다익스트라를 이용하여 플로이드-와샬 알고리즘을 구현한다고 하면 출발 정점을 모든 정점의 개수만큼 설정해 주면 된다.

  순차 탐색 방법으로 다익스트라를 구현하면 O(V^2)이고, 모든 정점을 출발 정점으로 한다고 하면 O(V * V^2) = O(V^3)이 되게 된다. 플로이드-와샬 알고리즘의 시간복잡도 또한 O(V^3)으로 같다. 하지만 플로이드-와샬 알고리즘의 구현은 다익스트라에 비해 매우 간단하므로 해당 방법을 익혀놓도록 하자.

 

2. 동작방식 🐕

  플로이드-와샬은 DP를 이용한다. 

  DP[i][j][k]는 정점 {1, 2,..., k}만을 경유 가능한 정점들로 생각하고, 정점 i로부터 정점 j까지의 모든 경로 중 가장 짧은 경로의 거리이다. 이때, {1, 2,..., k}에 속한 모든 정점들을 반드시 경유하는 게 아니라 경유를 할 수도 있고 안 할 수도 있다는 것에 주의하자.

  그러면 DP[i][j][k]은 어떻게 표현할 수 있을까? DP[i][j][k] = min(DP[i][j][k-1], DP[i][k][k-1] + DP[k][j][k-1])라고 할 수 있다. 

• DP[i][j][k-1] : 원소 k를 고려하지 않고 {1, 2,..., k-1}의 원소만 고려한 경우
• DP[i][k][k-1] + DP[k][j][k-1] : {1, 2,..., k-1}의 원소를 고려하였지만 k를 경유하기 때문에 결국 {1, 2,..., k}를 고려하는 경우

  즉, DP[i][j][k]는 '{1, 2,..., k-1}만 고려한 경우'와 'k를 무조건 포함하고 {1, 2,..., k}를 고려하는 경우' 중에 최단 경로를 선택하는 것이다. (DP의 원리를 알고 있다면 쉽게 이해할 수 있을 것이다.)
  이를 코드로 간단하게 표현하면 아래와 같다.

V ← Vertext
for k ← 1 to n
  for i ← 1 to n (i != k)
    for j ← 1 to n ( j != k , j != i)
      DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]);

  3차원 배열로 생각했지만 2차원으로 표현할 수 있었던 이유는 무엇일까? 바로 k가 반복문을 돌기 때문이다. DP[i][j] = Math.min(DP[i][j], DP[i][k] + DP[k][j])에서 좌항은 {1, 2,..., k}까지 고려한 DP이고 우항은 {1, 2,..., k-1}까지 고려한 DP이다. 'k가 오름차순으로 반복문을 도는 것'과 'i, j, k가 같은 상황은 고려하지 않는 것' 때문에 3차원 배열이 아닌 2차원 배열만 사용해서 표현할 수 있다.

 

3. 구현(JAVA) 🦮

  자기 자신으로 가는 가중치는 0으로 설정한다. 그리고 초기 값의 경우 경로가 존재하는 경우에는 경로의 가중치로, 경로가 존재하지 않는다면 INF(무한대)로 설정한다. 그래야지 k가 증가하면서 비교할 때 최단 경로 값으로 변경이 되기 때문이다. 이때 (INF+INF)등으로 인해 오버플로우가 나지 않도록 주의해야 한다.

[입력데이터]
0 3 8 0 -4
0 0 0 1 7
0 4 0 0 0
2 0 -5 0 0
0 0 0 6 0

static final int INF = 999999;
static int V;
static int[][] DP;
static String[] ss;

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

    V = 5;
    DP = new int[V][V];

    for(int i = 0; i < V; i++) {
        ss = in.readLine().split(" ");
        for(int j = 0; j < V; j++) {
            DP[i][j] = Integer.parseInt(ss[j]);
            // 경로가 없는 경우
            if((i != j) && (DP[i][j] == 0)) {
                DP[i][j] = INF;
            }
        }
    }

    for(int k = 0; k < V; k++) {
        for(int i = 0; i < V; i++) {
            if(i == k)
                continue;
            for(int j = 0; j < V; j++) {
                if((j == k) || (j == i))
                    continue;

                DP[i][j] = Math.min(DP[i][j], DP[i][k] + DP[k][j]);
            }
        }
    }

    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            System.out.print(DP[i][j] + " ");
        }
        System.out.println();
    }
}

[출력데이터]
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0