[CS기초] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘 개요

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 지점에서 다른 모든 지점까지의 최단 경로를 한꺼번에 구하는 알고리즘입니다. 이는 다익스트라 알고리즘과 달리 각 단계를 수행할 때마다 특정한 노드를 중간 지점으로 설정하여, 모든 노드 간의 경로를 동적으로 갱신하는 특징이 있습니다.

 

노드의 개수가 N개라면, 이 알고리즘은 N개의 단계를 거칩니다. 각 단계는 하나의 노드를 정해 '중간 경유 노드'로 두고, 이 노드를 거쳐 가는 경로를 고려해 최단 거리를 갱신합니다. 매 단계마다 2차원 배열(모든 노드 간 최단 거리)을 갱신하는데, 이때의 시간 복잡도는 단계마다 O(N²)입니다. 따라서 최종적인 시간 복잡도는 O(N³)이 됩니다.

 

플로이드-워셜 알고리즘은 모든 노드 간의 최단 거리를 담는 2차원 배열을 사용하며, 점화식을 활용해 최적의 값을 찾기 때문에 다이나믹 프로그래밍(DP)으로 분류됩니다. 각 단계에서는 다음과 같은 점화식을 통해 최단 거리를 갱신합니다.

 

 

이는 간단히 말하면 'A에서 B로 바로 이동하는 비용'과 'A에서 K라는 특정 노드를 거쳐 B로 이동하는 비용'을 비교하여, 더 적은 값을 선택하겠다는 의미입니다. 즉, 중간 노드를 거쳐 가는 경로가 더 짧다면 최단 경로 정보를 갱신합니다.

 

 

파이썬에서 플로이드-워셜 알고리즘의 구현

INF = int(1e9)  # 무한을 의미하는 값 10억 설정

# 노드 개수 및 간선 개수 입력
v = int(input())
e = int(input())
# 2차원 최단 거리 테이블 선언, 모든 값을 무한으로 초기화
distance = [[INF] * (v+1) for _ in range(v+1)]
# 자기 자신에서 자기 자신으로 가는 비용을 0으로 초기화
for i in range(1, v+1):
    for j in range(1, v+1):
        if i == j:
            distance[i][j] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(e):
    a, b, c = map(int, input().split())
    distance[a][b] = c
    
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, v+1):
    for i in range(1, v+1):
        for j in range(1, v+1):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

# 수행된 결과 출력
for i in range(1, v+1):
    for j in range(1, v+1):
        # 도달할 수 없는 경우, 무한(INFINITY)을 출력
        if distance[i][j] == INF:
            print("INFINITY", end=' ')
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(distance[i][j], end=' ')
    print()