anonymous.rs

알고리즘: 플로이드-워셜 (Floyd-Warshall Algorithm)

8 min read

플로이드-워셜 (Floyd-Warshall) 알고리즘 완벽 가이드

다익스트라(Dijkstra) 알고리즘이 ‘하나의 출발점’에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다면, 모든 정점에서 모든 정점까지의 최단 경로를 한 번에 구해야 할 때는 어떻게 해야 할까요?

이때 사용하는 알고리즘이 바로 플로이드-워셜(Floyd-Warshall) 알고리즘입니다.

1. 플로이드-워셜 알고리즘이란?

플로이드-워셜 알고리즘은 그래프에서 모든 노드 쌍 간의 최단 경로를 구하는 알고리즘입니다. (All-to-All Shortest Path)

다익스트라 알고리즘이 그리디(Greedy) 알고리즘을 기반으로 매 순간 가장 짧은 경로를 선택한다면, 플로이드-워셜 알고리즘은 **동적 계획법(Dynamic Programming, DP)**을 기반으로 합니다.

핵심 아이디어: “거쳐 가는 노드”

플로이드-워셜의 가장 중요한 핵심은 **“A에서 B로 가는 최단 경로는, A에서 바로 B로 가는 것과 A에서 특정 노드 K를 거쳐서 B로 가는 것 중 더 짧은 것이다”**라는 점입니다.

즉, 노드 부터 까지 순차적으로 ‘거쳐 가는 노드(K)‘로 설정하면서, 모든 노드 쌍 에 대해 최단 거리를 업데이트합니다.

  • 점화식:

2. 알고리즘 동작 과정

  1. 2차원 거리 테이블 초기화:
    • 자기 자신으로 가는 거리(대각선)는 0으로 초기화합니다.
    • 직접 연결된 간선이 있다면 그 가중치로 초기화합니다.
    • 직접 연결되지 않은 노드 간의 거리는 무한대(INF)로 초기화합니다.
  2. 3중 반복문 수행:
    • 첫 번째 반복문(K): 거쳐 가는 노드
    • 두 번째 반복문(A): 출발 노드
    • 세 번째 반복문(B): 도착 노드
    • A -> B의 기존 거리와 A -> K -> B의 거리를 비교하여 더 작은 값으로 2차원 테이블을 갱신합니다.

3. 파이썬(Python) 구현 예시

플로이드-워셜 알고리즘은 구현이 매우 직관적이고 짧다는 장점이 있습니다. 코딩 테스트에서는 주로 2차원 리스트를 사용합니다.

# 무한대 값을 의미하는 INF 설정 (10억)
INF = int(1e9)
 
# 노드의 개수 및 간선의 개수
n = 4
m = 7
 
# 2차원 거리 테이블을 만들고, 모든 값을 무한대로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
 
# 1. 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0
 
# 2. 각 간선에 대한 정보를 입력받아 그 값으로 초기화 (가중치 그래프)
# A -> B 가는 비용을 C라고 가정
edges = [
    (1, 2, 4), (1, 4, 6), (2, 1, 3), (2, 3, 7), 
    (3, 1, 5), (3, 4, 4), (4, 3, 2)
]
for a, b, c in edges:
    graph[a][b] = c
 
# 3. 플로이드-워셜 알고리즘 수행 (핵심 로직: 3중 for문)
# k: 거쳐가는 노드, a: 출발 노드, b: 도착 노드
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            # a에서 b로 가는 기존 거리와, k를 거쳐가는 거리를 비교하여 최솟값 갱신
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
 
# 결과 출력
print("모든 노드에서 모든 노드로 가는 최단 거리:")
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print("INF", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()
 
# [예상 출력]
# 0 4 8 6 
# 3 0 7 9 
# 5 9 0 4 
# 7 11 2 0

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

  • 시간 복잡도: (V는 정점의 개수)
    • 거쳐 가는 노드, 출발 노드, 도착 노드에 대해 각각 번씩 3중 반복문을 수행하므로 시간 복잡도는 이 됩니다.
    • 따라서 정점의 개수가 500개 이하인 같이 매우 작은 그래프에서만 사용 가능합니다. 노드가 1,000개를 넘어가면 시간 초과(TLE)가 발생할 확률이 높습니다.
  • 공간 복잡도:
    • 모든 노드 쌍 간의 거리를 저장해야 하므로 2차원 리스트(배열)를 사용합니다.

5. 다익스트라(Dijkstra) vs 플로이드-워셜(Floyd-Warshall)

인터뷰에서 두 최단 경로 알고리즘의 차이를 묻는 경우가 많으므로 아래 표를 숙지하는 것이 좋습니다.

비교 항목다익스트라 (Dijkstra)플로이드-워셜 (Floyd-Warshall)
목적한 노드에서 다른 모든 노드까지의 최단 경로모든 노드에서 다른 모든 노드까지의 최단 경로
알고리즘 기반그리디 (Greedy) 알고리즘동적 계획법 (Dynamic Programming)
자료구조1차원 배열 + 우선순위 큐(Min Heap)2차원 배열 (인접 행렬)
시간 복잡도 (빠름) (매우 느림)
음수 가중치처리 불가음수 사이클이 없다면 처리 가능
사용 조건정점과 간선이 많을 때 주로 사용정점의 개수가 매우 적을 때 (보통 500개 이하)

요약

플로이드-워셜 알고리즘은 코드가 매우 짧고 구현이 쉬운 강력한 ‘모든 쌍 최단 경로’ 알고리즘입니다. 하지만 이라는 무거운 시간 복잡도를 가지므로, 문제에서 주어지는 노드(정점)의 최대 개수를 반드시 확인하고 사용해야 합니다. (노드가 100~300개 수준이라면 플로이드-워셜을 적극 고려해 보세요!)

Graph View