플로이드-워셜 (Floyd-Warshall)

개념

모든 정점 쌍 간의 최단 경로를 구하는 알고리즘

동적 프로그래밍 방식으로 중간 정점을 거쳐가며 최단 경로 갱신

---

시간복잡도

구현 방식	시간복잡도
기본 구현	O(V³)
공간복잡도	O(V²)

---

특징

장점

• 모든 쌍 최단 경로: 한 번에 모든 정점 간 최단 경로
• 음수 가중치 가능: 음수 간선 처리 가능
• 구현 간단: 3중 반복문으로 구현
• 음수 사이클 탐지: 대각선 원소로 확인

단점

• 느린 속도: O(V³) - 정점 많으면 매우 느림
• 메모리 사용: O(V²) 2차원 배열 필요

적용 조건

• 정점 수가 적음: V ≤ 500 정도
• 모든 쌍 필요: 모든 정점 간 거리 필요
• 음수 가중치 가능

---

구현 방법

기본 구현

def floyd_warshall(n, edges):
    """플로이드-워셜 알고리즘"""
    # 거리 배열 초기화
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    # 자기 자신으로의 거리는 0
    for i in range(n):
        dist[i][i] = 0
 
    # 간선 정보 입력
    for u, v, weight in edges:
        dist[u][v] = weight
        # 무방향 그래프면 양방향 추가
        # dist[v][u] = weight
 
    # 플로이드-워셜 알고리즘
    for k in range(n):  # 중간 정점
        for i in range(n):  # 출발 정점
            for j in range(n):  # 도착 정점
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
 
    return dist
 
# 테스트
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, -2),
    (1, 3, 2),
    (2, 3, 3)
]
 
dist = floyd_warshall(4, edges)
for row in dist:
    print(row)
 
# 출력:
# [0, 4, 2, 5]
# [inf, 0, -2, 1]
# [inf, inf, 0, 3]
# [inf, inf, inf, 0]
 
# 시간복잡도: O(V³)
# 공간복잡도: O(V²)

---

경로 복원 구현

def floyd_warshall_with_path(n, edges):
    """경로 추적"""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    next_node = [[-1] * n for _ in range(n)]
 
    # 초기화
    for i in range(n):
        dist[i][i] = 0
 
    for u, v, weight in edges:
        dist[u][v] = weight
        next_node[u][v] = v
 
    # 플로이드-워셜
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_node[i][j] = next_node[i][k]
 
    return dist, next_node
 
def reconstruct_path(next_node, start, end):
    """경로 복원"""
    if next_node[start][end] == -1:
        return []
 
    path = [start]
    current = start
 
    while current != end:
        current = next_node[current][end]
        path.append(current)
 
    return path
 
# 테스트
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, -2),
    (1, 3, 2),
    (2, 3, 3)
]
 
dist, next_node = floyd_warshall_with_path(4, edges)
path = reconstruct_path(next_node, 0, 3)
print(f"0→3 최단 거리: {dist[0][3]}")  # 5
print(f"0→3 경로: {path}")              # [0, 1, 2, 3]

---

음수 사이클 탐지

def detect_negative_cycle_floyd(n, edges):
    """음수 사이클 탐지"""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    for i in range(n):
        dist[i][i] = 0
 
    for u, v, weight in edges:
        dist[u][v] = weight
 
    # 플로이드-워셜
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != INF and dist[k][j] != INF:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
 
    # 음수 사이클 확인 (대각선 원소가 음수면 사이클)
    for i in range(n):
        if dist[i][i] < 0:
            return True
 
    return False
 
# 테스트
# 음수 사이클 있는 경우
edges = [
    (0, 1, 1),
    (1, 2, -3),
    (2, 0, 1)
]
print(detect_negative_cycle_floyd(3, edges))  # True

---

동작 과정

그래프:
    0 --4--> 1
    |        |
    3       -2
    ↓        ↓
    2 --3--> 3

초기 거리 행렬:
    0   1   2   3
0 [ 0   4   3  INF]
1 [INF  0  -2   2 ]
2 [INF INF  0   3 ]
3 [INF INF INF  0 ]

k=0 (0번 정점 경유):
  1→0→2: INF (도달 불가)
  2→0→1: INF (도달 불가)
  ... (변화 없음)

k=1 (1번 정점 경유):
  0→1→2: 4+(-2) = 2 < 3 ✓
  0→1→3: 4+2 = 6 < INF ✓
    0   1   2   3
0 [ 0   4   2   6 ]
1 [INF  0  -2   2 ]
2 [INF INF  0   3 ]
3 [INF INF INF  0 ]

k=2 (2번 정점 경유):
  0→2→3: 2+3 = 5 < 6 ✓
  1→2→3: -2+3 = 1 < 2 ✓
    0   1   2   3
0 [ 0   4   2   5 ]
1 [INF  0  -2   1 ]
2 [INF INF  0   3 ]
3 [INF INF INF  0 ]

k=3 (3번 정점 경유):
  변화 없음

최종 거리 행렬:
    0   1   2   3
0 [ 0   4   2   5 ]
1 [INF  0  -2   1 ]
2 [INF INF  0   3 ]
3 [INF INF INF  0 ]

---

템플릿

def floyd_warshall_template(n, edges):
    # 1. 초기화
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    for i in range(n):
        dist[i][i] = 0
 
    for u, v, weight in edges:
        dist[u][v] = weight
 
    # 2. 3중 반복 (중간 정점 k 경유)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
    return dist

---

핵심 요약

개념	설명
원리	DP - 중간 정점 경유 최소화
시간복잡도	O(V³)
공간복잡도	O(V²)
적용 조건	모든 쌍 최단 경로
특징	음수 가중치 가능

---

다른 알고리즘과 비교

알고리즘	시간복잡도	용도	음수 가중치
다익스트라	O((V+E) log V)	단일 출발점	불가
벨만-포드	O(VE)	단일 출발점	가능
플로이드-워셜	O(V³)	모든 쌍	가능
다익스트라 V번	O(V(V+E) log V)	모든 쌍	불가

---

주의사항

1. 반복문 순서

# 올바른 순서: k → i → j
for k in range(n):      # 중간 정점
    for i in range(n):  # 출발 정점
        for j in range(n):  # 도착 정점
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
# 잘못된 순서
for i in range(n):
    for j in range(n):
        for k in range(n):  # 잘못됨!

2. INF 처리

# INF + INF 오버플로우 방지
if dist[i][k] != INF and dist[k][j] != INF:
    if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]

3. 정점 수 제한

# O(V³)이므로 V가 크면 시간 초과
# V ≤ 500 정도가 적당
# V > 500이면 다익스트라 여러 번 실행 고려

---

자주 나오는 문제 유형

1. 모든 쌍 최단 경로

문제: 모든 정점 간 최단 거리

def all_pairs_shortest_path(n, edges):
    """모든 쌍 최단 경로"""
    dist = floyd_warshall(n, edges)
 
    # 결과 출력
    for i in range(n):
        for j in range(n):
            if dist[i][j] == float('inf'):
                print("INF", end=" ")
            else:
                print(dist[i][j], end=" ")
        print()
 
    return dist
 
# 테스트
edges = [
    (0, 1, 4),
    (0, 2, 3),
    (1, 2, -2),
    (1, 3, 2),
    (2, 3, 3)
]
 
all_pairs_shortest_path(4, edges)

---

2. 경유지를 반드시 거치는 최단 경로

문제: A → B → C 최단 경로

def shortest_path_via_nodes(dist, start, via_nodes, end):
    """특정 노드들을 반드시 거치는 최단 경로"""
    # start → via[0] → via[1] → ... → end
    total_dist = 0
    current = start
 
    for via in via_nodes:
        if dist[current][via] == float('inf'):
            return float('inf')
        total_dist += dist[current][via]
        current = via
 
    if dist[current][end] == float('inf'):
        return float('inf')
 
    total_dist += dist[current][end]
    return total_dist
 
# 테스트
edges = [
    (0, 1, 2), (1, 2, 3), (2, 3, 1),
    (0, 2, 10), (1, 3, 5)
]
 
dist = floyd_warshall(4, edges)
# 0 → 1 → 2 → 3 경로
print(shortest_path_via_nodes(dist, 0, [1, 2], 3))  # 6

---

3. 사이클의 최소 길이

문제: 최소 길이 사이클 찾기

def shortest_cycle(n, edges):
    """최소 길이 사이클"""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    for u, v, weight in edges:
        dist[u][v] = weight
 
    min_cycle = INF
 
    # k를 거치지 않는 최단 경로로 사이클 확인
    for k in range(n):
        # k를 추가하기 전에 사이클 확인
        for i in range(n):
            for j in range(n):
                if i != j and dist[i][j] != INF and dist[j][i] != INF:
                    min_cycle = min(min_cycle, dist[i][j] + dist[j][i])
 
        # k를 중간 정점으로 추가
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
    return min_cycle if min_cycle != INF else -1
 
# 테스트
edges = [
    (0, 1, 1),
    (1, 2, 2),
    (2, 0, 3),
    (1, 3, 4),
    (3, 1, 5)
]
 
print(shortest_cycle(4, edges))  # 6 (0→1→2→0)

---

4. 친구 관계의 거리

문제: 모든 사람 간의 친구 관계 단계

def friend_distance(n, friendships):
    """친구 관계 거리"""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    for i in range(n):
        dist[i][i] = 0
 
    # 친구 관계는 거리 1
    for u, v in friendships:
        dist[u][v] = 1
        dist[v][u] = 1
 
    # 플로이드-워셜
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
    return dist
 
# 테스트
friendships = [(0, 1), (1, 2), (2, 3), (0, 3)]
dist = friend_distance(4, friendships)
 
# 0과 2의 친구 단계
print(f"0과 2의 거리: {dist[0][2]}")  # 2 (0→1→2 or 0→3→2)

---

5. 회사 위치 선정 (케빈 베이컨)

문제: 모든 정점까지의 거리 합이 최소인 정점

def find_center_node(n, edges):
    """중심 정점 찾기 (케빈 베이컨)"""
    dist = floyd_warshall(n, edges)
 
    min_sum = float('inf')
    center = -1
 
    for i in range(n):
        total = sum(dist[i])
        if total < min_sum:
            min_sum = total
            center = i
 
    return center, min_sum
 
# 테스트
edges = [
    (0, 1, 1), (0, 2, 1),
    (1, 3, 1), (2, 3, 1),
    (3, 4, 1)
]
 
center, min_sum = find_center_node(5, edges)
print(f"중심 정점: {center}, 거리 합: {min_sum}")

---

6. 역방향 최단 경로

문제: 간선 방향을 모두 반대로 했을 때 최단 경로

def reverse_shortest_path(n, edges):
    """역방향 최단 경로"""
    # 정방향
    forward_edges = edges
    forward_dist = floyd_warshall(n, forward_edges)
 
    # 역방향 간선 생성
    reverse_edges = [(v, u, w) for u, v, w in edges]
    reverse_dist = floyd_warshall(n, reverse_edges)
 
    return forward_dist, reverse_dist
 
# 왕복 최단 거리
def round_trip_distance(forward_dist, reverse_dist, start, end):
    """왕복 거리"""
    go = forward_dist[start][end]
    back = reverse_dist[start][end]
    return go + back if go != float('inf') and back != float('inf') else float('inf')

---

추천 연습 문제

기초

• 백준 11404번 - 플로이드
• 백준 14938번 - 서강그라운드

중급

• 백준 1389번 - 케빈 베이컨의 6단계 법칙
• 백준 1956번 - 운동
• 백준 2458번 - 키 순서

고급

• 백준 1719번 - 택배
• 백준 1613번 - 역사

---

최적화 기법

1. 메모리 절약 (경로 불필요 시)

def floyd_warshall_memory_optimized(n, edges):
    """메모리 최적화 - 경로 추적 없음"""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    for i in range(n):
        dist[i][i] = 0
 
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # 중복 간선 처리
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
    return dist

---

2. 비트마스크 최적화 (정점 제한)

def floyd_warshall_bitmask(n, edges, allowed_nodes):
    """특정 정점만 경유 가능"""
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
 
    for i in range(n):
        dist[i][i] = 0
 
    for u, v, w in edges:
        dist[u][v] = w
 
    # allowed_nodes만 경유
    for k in allowed_nodes:
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
    return dist

---

언제 사용할까?

사용 가능

• 모든 쌍 필요: 모든 정점 간 최단 거리
• 정점 수 적음: V ≤ 500
• 음수 가중치: 음수 간선 있음
• 간단한 구현: 빠르게 구현 필요

사용 불가

• 정점 많음: V > 500 (시간 초과)
• 단일 출발점: 다익스트라가 빠름
• 희소 그래프: 다익스트라 V번이 빠름

결론: 작은 그래프에서 모든 쌍 최단 경로가 필요할 때 최적!