[PS] Floyd-Warshall

Hood·2025년 2월 9일

floyd-warshall ps

PS

목록 보기

15/15

✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘

소속 중인 A&I 동아리에서 코딩 역량을 강화하기 위해
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 Kotlin을 기반으로 작성하였습니다.

들어가기 전에

지난번에 살펴본 다익스트라 알고리즘은 하나의 노드에서 특정 노드까지의 최단 경로를 구하는 알고리즘이었습니다.
이번에 알아볼 플로이드-워셜 알고리즘은 모든 노드에서 다른 노드까지의 최단 경로를 모두 계산하는 알고리즘입니다.
즉, 두 알고리즘은 모두 최단 경로를 구하지만, 어떤 범위의 경로를 구하느냐에서 차이가 있습니다.
이 점을 먼저 구분하고 들어가겠습니다.

Floyd-Warshall

플로이드-워셜 알고리즘은 모든 노드 쌍 사이의 최단 경로를 계산할 때 사용할 수 있습니다.
플로이드-워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로, 단계별로 거쳐 가는 노드를 기준으로 최단 거리를 갱신해 나갑니다.
다만 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 따로 찾을 필요는 없습니다.

플로이드-워셜은 다익스트라와 달리 2차원 테이블에 최단 거리 정보를 저장합니다.
이러한 특징 때문에 플로이드-워셜 알고리즘은 DP 유형으로 분류됩니다.

DP?

하나의 큰 문제를 여러 개의 작은 문제로 나누어 해결하는 방법을 말합니다.

따라서 플로이드-워셜 알고리즘은 다이나믹 프로그래밍처럼 점화식을 바탕으로 최단 거리를 계산합니다.

$D_{ab}=min(D_{ab}, D_{ak} + D_{kb})$

예를 들면

다음과 같은 그래프가 있다고 가정해 보겠습니다.
초기 테이블은 다음과 같습니다.
이때 갈 수 없는 경로는 INF로 표시하였습니다.

1번 노드부터 플로이드-워셜을 수행한다고 하면, 다음과 같은 점화식을 세울 수 있습니다.

1번 노드를 거쳐 가는 모든 경우

실제로는 테이블의 모든 값이 변경되지는 않습니다.
기존 값보다 더 짧은 경로가 발견되는 경우에만 값이 갱신됩니다.

2번 노드를 거쳐 가는 모든 경우

3번 노드를 거쳐 가는 모든 경우

4번 노드를 거쳐 가는 모든 경우

최종적으로 다음과 같은 결과를 얻을 수 있습니다.

In Kotlin

package programmers.Lv0.week21

import kotlin.math.min

fun main() {
    val graph = listOf(
        emptyList(),
        listOf(Pair(2, 3), Pair(4, 6)),
        listOf(Pair(1, 4), Pair(3, 7)),
        listOf(Pair(1, 5), Pair(4, 2)),
        listOf(Pair(3, 4))
    )

    val INF = 1_000_000_000L

    // 최단 경로를 기록할 2차원 배열 선언
    val dist = Array(5) { LongArray(5) { INF } }

    // 자기 자신으로 가는 최단 경로는 0으로 초기화
    for (i in 1..4) {
        dist[i][i] = 0
    }

    // 그래프 정보를 통해 인접 노드 가중치 초기화
    for (i in 1..4) {
        for ((node, weight) in graph[i]) {
            dist[i][node] = weight.toLong()
        }
    }

    // 플로이드-워셜
    repeat(4) { k ->
        repeat(4) { i ->
            repeat(4) { j ->
                dist[i + 1][j + 1] =
                    min(dist[i + 1][j + 1], dist[i + 1][k + 1] + dist[k + 1][j + 1])
            }
        }
    }

    for (i in 1..4) {
        for (j in 1..4) {
            print("${dist[i][j]} ")
        }
        println()
    }
}