Floyd-Warshall, 플로이드 워샬 알고리즘

그래프 문제에서 최단 경로를 구하는 알고리즘은 다음과 같다.

Dijkstra	다익스트라	한 지점에서 다른 모든 지점까지 최단 거리	양의 가중치만	O(ElogV)
Bellman-ford	밸만-포드	한 지점에서 다른 모든 지점까지 최단 거리	음의 가중치 허용	O(VE)
Floyd-Warshall	플로이드 워샬	모든 지점에서 다른 모든 지점까지 최단 거리	음의 가중치 허용	O(V^3)

 

다익스트라와 밸만 포드에 대해서는 다음 포스팅에서 알아볼 수 있다.

다익스트라, Dijkstra Algorithm

Bellman-Ford 알고리즘

 

---

Floyd-Warshall, 플로이드 워샬

❓ Floyd-Warshall, 플로이드 워샬

그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘이다. 음의 사이클이 없는 한 음의 가중치가 있어도 잘 실행되는 최단 거리 알고리즘이다.

 

기본 컨셉

 

기본 컨셉은 하나이다. DP 개념을 활용한다.

정점 i, j 사이 모든 경유지를 탐색해서 그 중 최단 경로를 찾는다. 그래프의 정점이 1~V까지이면, 경유지 K는 이 모든 정점을 경유지로 하는 경로를 탐색한다.

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

 

알고리즘 동작 과정

1. 2차원 배열을 만들고 그래프의 간선의 정보를 저장한다.
   1. 두 정점이 직접적으로 연결되어 있지 않으면 INF값, 자기 자신으로의 거리는 0으로 설정한다.
2. 경유지를 1~V까지 순회한다
   1. 간선 정보를 저장한 2차원 배열을 순회하며 (i~j)까지의 거리와 (i~k + k~j)까지의 거리 중 짧은 값으로 업데이트한다.

 

예시

이 그래프를 토대로 각 정점간의 거리를 저장한 2차원 배열을 만들어보자.

	1	2	3	4
1	0	4	-1	8
2	INF	0	-2	-10
3	INF	INF	0	3
4	INF	INF	INF	0

 

 

경유지를 1로 설정했을 때는 다음과 같다.

	1	2	3	4
1	0	4	-1	8
2	INF	0	-2	-10
3	INF	INF	0	3
4	INF	INF	INF	0

 

1을 거쳐서 가는 경로가 없기 때문에, 즉 1열이 모두 INF 값이기 때문에 아무것도 변화하지 않는다.

 

 

경유지를 2로 설정했을 때는 다음과 같다.

	1	2	3	4
1	0	4	-1	8 ⇒ -6
2	INF	0	-2	-10
3	INF	INF	0	3
4	INF	INF	INF	0

 

1은 2를 거쳐서 다른 노드로 갈 수 있기 때문에, 1 → 4보다, 1 → 2 → 4가 더 짧아서 -6으로 업데이트 되었다.

 

 

경유지를 3으로 설정했을 때는 다음과 같다.

	1	2	3	4
1	0	4	-1	-6
2	INF	0	-2	-10
3	INF	INF	0	3
4	INF	INF	INF	0

 

1 → 3, 2 → 3으로 갈 수 있다.

• 1→ 3 → 다른 노드
  • 1 → 3 → 4만 가능하다.
    • 하지만 1 → 3 → 4는 2이고, 1 → 4는 -6이기 때문에 업데이트 되지 않는다.
• 2 → 3 → 다른 노드
  • 2 → 3 → 4만 가능하다
    • 하지만 2 → 3 → 4는 1이고, 2 → 4는 -10이기 때문에 업데이트 되지 않는다.

따라서 표는 업데이트 되지 않는다.

 

 

경유지를 4로 설정하면 다음과 같다.

	1	2	3	4
1	0	4	-1	-6
2	INF	0	-2	-10
3	INF	INF	0	3
4	INF	INF	INF	0

 

(1 → 4), (2 → 4), (3 → 4) 모두 가능하지만, 4에서 갈 수 있는 노드가 없기 때문에 표는 업데이트 되지 않는다.

 

 

이렇게 최종 배열이 나왔고, 이것이 바로 플로이드 워샬을 적용한, 모든 노드에서 모든 노드로 가는 최단 거리 배열이다.

	1	2	3	4
1	0	4	-1	-6
2	INF	0	-2	-10
3	INF	INF	0	3
4	INF	INF	INF	0

---

코드

아래 문제를 풀어보면서 코드를 정리해보자.

11404번: 플로이드

 

자료구조

 

우선 플로이드 알고리즘에 필요한 자료구조는 간선 정보를 저장한 graph 하나뿐이다. 이 그래프를 가지고 업데이트하고 계속 할 것이다.

또한 무한의 값으로 사용할 INF 값도 정의해주자. 아래에서 두 INF 값을 더하는 코드가 있기 때문에 / 2 + 1을 해주었다.

static int[][] graph;
static int INF = Integer.MAX_VALUE / 2 -1;

 

간선 정보를 입력 받기 전, graph를 초기화해주어야 한다. 모든 값을 INF로 채우고, 자기 자신으로 가는 값은 0으로 바꿔준다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int M = Integer.parseInt(in.readLine());
graph = new int[N+1][N+1];
for (int i = 0; i < N+1; i++){
    Arrays.fill(graph[i], INF);
    graph[i][i] = 0; //자기자신은 0
}

 

간선 정보를 입력 받으며 최소인 값으로 갱신해준다. 문제에서 두 지점 사이의 간선이 여러 개일 수도 있다고 했기 때문에 최소로 갱신해주는 코드로 작성했다.

while(M -- > 0){
    StringTokenizer st = new StringTokenizer(in.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int cost = Integer.parseInt(st.nextToken());
    graph[a][b] = Math.min(graph[a][b], cost); //노선이 여러개일 수 있다고 했으니까
}

 

알고리즘을 수행하는 코드이다. 간단하다. 경유지를 돌면서, 모든 간선 정보를 업데이트 해주면 된다. DP와 비슷하다.

//floyd-warshall
//경유지
for (int k = 1; k <= N; k++){
    for (int i = 0; i <= N; i++){
        for (int j = 0; j <= N; j++){
            graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
        }
    }
}

 

그리고 이를 출력하는 코드이다.

StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N; i++){
    for (int j = 1; j <= N; j++){
       sb.append((graph[i][j] == INF)? 0 : graph[i][j]).append(" ");
   }
    sb.append("\\n");
}
System.out.println(sb);

 

전체 코드

package ps.ㄱSolving;

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

public class BOJ_G4_11404_플로이드 {
    static int[][] graph;
    static int INF = Integer.MAX_VALUE / 2 -1;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        int M = Integer.parseInt(in.readLine());
        graph = new int[N+1][N+1];
        for (int i = 0; i < N+1; i++){
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0; //자기자신은 0
        }
        while(M -- > 0){
            StringTokenizer st = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[a][b] = Math.min(graph[a][b], cost); //노선이 여러개일 수 있다고 했으니까
        }

        //floyd-warshall
        //경유지
        for (int k = 1; k <= N; k++){
            for (int i = 0; i <= N; i++){
                for (int j = 0; j <= N; j++){
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                sb.append((graph[i][j] == INF)? 0 : graph[i][j]).append(" ");
            }
            sb.append("\\n");
        }
        System.out.println(sb);
    }
}

---

참고자료

[Algorithm]Floyd-Warshall(플로이드-워샬 알고리즘)

 

알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고