알고리즘/개념

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

두다다 2025. 2. 9. 16:31
반응형

최단경로를 탐색하는 플로이드-와샬(Floyd-Warshall) 알고리즘에 대해 알아보자.

플로이드-와샬 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 거리를 찾는 동적 프로그래밍(Dynamic Programming) 알고리즘이다.

(만약 최단거리의 경로를 구하고 싶다면 복원 로직의 추가가 필요하다.)

1. 동작방식의 이해

플로이드-와샬 알고리즘의 동작 방식은 아주 간단하다.

  1. 모든 정점 쌍(i,j)에 대해, 중간 정점 k를 경유하는 경로가 기존 경로보다 짧은지 검사
  2. 각 단계에서 k번째 정점을 거쳐가는 모든 경우를 고려

즉 아래와 같은 세 노드가 있을 때, 기존에 주어진 i → j 의 길이와 노드 k가 중간에 추가된 i → k → j 를 비교하여 i → j 의 길이를 더 작은 값으로 갱신하는 것이다.

점화식은 아래와 같다.

$DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j])$

이를 이용한 의사코드(Pseudo code)는 다음과 같다.

// 모든 정점 쌍 사이의 최단 거리를 저장할 2차원 배열 dist[][]
// 인접 행렬로 초기화된 상태에서 시작
// V는 정점의 개수

FloydWarshall(dist[1..V][1..V]):
    // k는 거쳐가는 정점
    for k from 1 to V:
        // i는 출발 정점
        for i from 1 to V:
            // j는 도착 정점
            for j from 1 to V:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

2. 누락되는 부분은 없을까?

플로이드 와샬 알고리즘에서 누락되는 경우의 수가 발생할 여지는 없을까?

즉, 이후 단계의 결과가 이전 단계의 결과를 번복시키는 경우는 없을까?

플로이드 와샬 알고리즘의 핵심 원리는 다음과 같다.

  • 단계적 처리: 알고리즘은 k=0부터 k=n-1까지 순차적으로 처리한다.
  • 최적화 조건: k번째 단계에서는 "i에서 j로 가는 경로"와 "i에서 k를 거쳐 j로 가는 경로" 중 더 짧은 것을 선택한다.
  • 누적 최적화: 각 k 단계마다 모든 정점 쌍(i, j)에 대해 이 최적화를 적용한다.

예를들어, k=n일 때, 이미 k=0 ~ n-1을 경유점으로 고려한 최단 경로이다.(k가 0부터 순차적으로 증가하도록 설계하였을 경우를 가정함)

점화식을 통해 이해하자면,
dp[k][i][j] = k번째 단계에서 i에서 j까지의 최단 거리 (여기서 dp[k]는 0부터 k까지의 정점만을 중간 정점으로 사용할 수 있을 때의 최단 거리) 라고 할 때, 알고리즘은 다음과 같은 관계를 만족한다.

$dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])$

이 식에서 k=10일 경우, k=9의 결과에만 의존하며 k=7일 때의 결과에 영향을 미칠 수 없다.

결론적으로, 이후 단계의 결과가 이전 단계의 결과에 영향을 미치는 경우의 수는 없다.

3. 예제

아래와 같이 4개의 정점에서 다른 곳을 이동하는 거리가 표현된 그래프가 존재한다.

최초 데이터를 정리하면 다음과 같다.

  • A에서 B로 이동하는 거리 5
  • A에서 C로 이동하는 거리 무한대(알 수 없음)
  • ...

k를 A부터 D까지 순회하며 최단경로를 찾아보자.(변동사항이 발생하는 경로만 별도 수식 표기)

1단계: k=A

  • $DP[B][D] = min(DP[B][D], DP[B][A] + DP[A][D]) → DP[B][D] = min(INF, 15)$
  • $DP[C][B] = min(DP[C][B], DP[C][A] + DP[A][B]) → DP[B][D] = min(INF, 7)$

2단계: k=B

  • $DP[A][C] = min(DP[A][C], DP[A][B] + DP[B][C]) → DP[A][C] = min(INF, 14)$

3단계: k=C

  • $DP[B][D] = min(DP[B][D], DP[B][C] + DP[C][D]) → DP[B][D] = min(15, 13)$
  • $DP[D][A] = min(DP[D][A], DP[D][C] + DP[C][A]) → DP[D][A] = min(INF, 5)$
  • $DP[D][B] = min(DP[D][B], DP[D][C] + DP[C][B]) → DP[D][B] = min(INF, 10)$

4단계(마지막): k=D

  • $DP[A][C] = min(DP[A][C], DP[A][D] + DP[D][C]) → DP[A][C] = min(14, 11)$

최종적으로 아래와 같은 최단거리 데이터를 구할 수 있다.

이를 Python 코드로 구현하면 아래와 같다.

INF = float('inf')  # 무한대 값 설정

# 그래프를 인접 행렬로 표현
graph = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
]

def floyd_warshall(graph):
    V = len(graph)  # 정점의 개수
    dist = [row[:] for row in graph]  # 그래프 복사

    # k = 거쳐가는 노드
    for k in range(V):
        # i = 출발 노드
        for i in range(V):
            # j = 도착 노드
            for j in range(V):
                # i에서 j로 가는 현재 거리와 k를 거쳐가는 거리를 비교
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

# 결과 출력을 위한 함수
def print_solution(dist):
    V = len(dist)
    print("최단 거리 행렬:")
    for i in range(V):
        for j in range(V):
            if dist[i][j] == INF:
                print("INF", end=" ")
            else:
                print(dist[i][j], end=" ")
        print()

# 알고리즘 실행
result = floyd_warshall(graph)
print_solution(result)

4. 시간복잡도 및 공간복잡도

  1. 시간복잡도
    • $O(V^3)$ - 세 개의 중첩된 반복문 사용
    • V는 정점의 개
  2. 공간복잡도
    • $O(V^2)$ - V*V 크기의 2차원 배열 필요

5. 특징

플로이드 와샬 알고리즘의 장점은 다음과 같다.

  • 간단한 코드(3중 for문) 구현
  • 음수 가중치 처리 가능
  • 모든 경로의 계산

단점은 다음과 같다.

  • 높은 시간 복잡도
  • 큰 메모리 사용
  • 동적 갱신의 비 효율성

결론적으로 아래와 같은 상황에서 사용되는 것이 효율적이라고 판단된다.

  • 정점 수가 적은 경우
  • 모든 쌍의 최단 경로가 필요한 경우
  • 그래프 변경이 빈번하지 않은 경
반응형