[알고리즘] 최단 경로 - Floyd-Warshall 알고리즘

1. Floyd-Warshall 알고리즘이란?

---

최단 경로는 크게 두 가지 경우로 나눌 수 있습니다.

one-to-all : 하나의 출발지에 대해 나머지 모든 노드까지의 최단 경로를 구한다. (Dijkstra 알고리즘, 벨만-포드 알고리즘)

all-to-all : 모든 노드에 대해 다른 모든 노드까지의 최단 경로를 구한다. (Floyd-Warshall 알고리즘)

 

플로이드 와샬은 all-to-all 에 대한 최단 경로를 구할 때 사용되는 알고리즘입니다.

5개의 노드가 있다고 가정했을 때, 1번 노드에서 2, 3, 4, 5번 노드까지의 최단 경로, 2번 노드에서 1, 3, 4, 5번 노드까지의 최단 경로, ...처럼 모든 노드에 대해 최단 경로를 구하기 때문에 비용을 저장하기 위해 2차원 배열이 필요합니다.

 

아래와 같은 그래프가 있다고 가정해보자.

[그림 1] 초기 그래프와 테이블 셋팅

위 테이블 세팅 값은 당장에 알 수 있는 간선의 비용입니다.
예를 들어, 1->5 로 가는 비용은 11이고 5->4로 가는 비용은 3입니다. 하지만, 직접적으로 1->4 로 가는 간선은 없습니다.
1->4로 갈려면 5를 거쳐야하기 때문입니다. 따라서 1->4는 INF값으로 초기셋팅을 해줍니다.

 

이제 Floyd-Warshall 알고리즘을 이용해 모든 노드에 대해 다른 모든 노드까지의 최단경로 비용을 구해보겠습니다.

Floyd-Warshall의 핵심은 '거쳐가는 정점'입니다. 코드를 먼저 보고난 후, 테이블을 채워나가 보겠습니다.

void floydWarshall() {
    for (int k = 1; k <= 5; k++) { // 거쳐가는 정점 
        for (int i = 1; i <= 5; i++) { // 출발지 정점
            for (int j = 1; j <= 5; j++) { // 목적지 정점
                arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
}

 

1->4번까지 거쳐가는 정점은 1개가 있고, 1->3번까지는 2개의 거쳐가는 정점이 있다는 걸 잘 기억해주세요. 🙂

위 제시된 그래프는 거쳐가는 정점이 3번부터 의미가 있으므로, k=3일때 갱신되는 테이블 셋팅을 보겠습니다.

[그림 2] k=3일때 갱신된 테이블 값

다음으로 k=4일 때는 테이블이 다음과 같이 갱신됩니다.

[그림 3] k=4일때 갱신된 테이블 값

마지막으로 k=5일 때는 테이블이 다음과 같이 갱신됩니다.

[그림 4] k=5일때 갱신된 테이블 값

즉, Floyd-Warshall 알고리즘을 이용하면 모든 노드에 대해 다른 모든 노드로의 최단경로를 쉽게 구할 수 있습니다.

2. 참고자료

---

[1] m.blog.naver.com