9. 플로이드-워샬 (Floyd-Warshall) — 전체 쌍 최단 경로, O(V³)

핵심 인사이트 (3줄 요약)

1. 본질: 플로이드-워샬 (Floyd-Warshall) 알고리즘은 동적 프로그래밍 (Dynamic Programming)으로 모든 정점 쌍 간 최단 거리를 O(V³)에 계산하는 전체 쌍 최단 경로 (All-Pairs Shortest Path, APSP) 알고리즘이다.
2. 가치: 음수 간선을 허용하고, V×V 행렬 3중 루프라는 단순한 구현으로 밀집 그래프의 모든 쌍 경로를 한 번에 구한다.
3. 판단 포인트: V ≤ 500 수준의 밀집 그래프에 적합하며, dp[k][k] < 0이면 음수 사이클이 존재함을 감지할 수 있다.

Ⅰ. 개요 및 필요성

플로이드-워샬 알고리즘은 그래프의 모든 정점 쌍 (i, j)에 대해 i에서 j까지의 최단 경로를 계산한다. 핵심 아이디어는 "중간 경유 정점 k를 0~V-1까지 순서대로 고려하여 경로를 점진적으로 개선"하는 것이다.

📢 섹션 요약 비유: 플로이드-워샬은 중간 기착지를 한 도시씩 추가하며 "이 도시를 경유하면 더 빠르냐?"를 모든 출발-도착 쌍에 대해 반복하는 방법이다.

Ⅱ. 아키텍처 및 핵심 원리

점화식 (Recurrence Relation)

dp[i][j] = i에서 j까지 정점 {0,...,k}만을 중간 경유할 때 최단 거리

dp[i][j][k] = min(
    dp[i][j][k-1],              // k를 경유하지 않음
    dp[i][k][k-1] + dp[k][j][k-1] // k를 경유함
)

공간 최적화: 2D 배열로 in-place 업데이트 가능
for k in 0..V:
  for i in 0..V:
    for j in 0..V:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ASCII 다이어그램 — 플로이드-워샬 행렬 갱신

┌─────────────────────────────────────────────────────────┐
│  그래프:  0─(3)→1, 0─(7)→2, 1─(2)→2, 2─(1)→0          │
│                                                         │
│  초기 dist (adj 행렬, ∞=무한):                           │
│       0    1    2                                       │
│  0 [  0,   3,   7 ]                                     │
│  1 [  ∞,   0,   2 ]                                     │
│  2 [  1,   ∞,   0 ]                                     │
│                                                         │
│  k=0 (0번 정점 경유) 후:                                  │
│       0    1    2                                       │
│  0 [  0,   3,   7 ]                                     │
│  1 [  ∞,   0,   2 ]                                     │
│  2 [  1,   4,   0 ]  ← dist[2][1] = dist[2][0]+dist[0][1] = 1+3=4 │
│                                                         │
│  k=1 후:                                                │
│  0 [  0,   3,   5 ]  ← dist[0][2] = 0+3+2=5 (0→1→2)   │
│  ...                                                    │
└─────────────────────────────────────────────────────────┘

알고리즘 단계별 동작

음수 사이클 검출

알고리즘 종료 후:
if dist[i][i] < 0 for any i:
    → 음수 사이클이 존재
    → 최단 경로 정의 불가 (무한히 작아짐)

📢 섹션 요약 비유: 음수 사이클 검출은 "자기 자신으로 돌아오는 여행 경비가 음수"인 경우를 찾는 것이다. 이런 사이클이 있으면 무한 반복으로 비용을 무한히 낮출 수 있어 최단 경로가 의미 없어진다.

Ⅲ. 비교 및 연결

최단 경로 알고리즘 비교

V=500일 때 플로이드-워샬 vs 다익스트라 반복

플로이드-워샬: 500³ = 125,000,000번 연산 (단 1회)
다익스트라×V: V × O((V+E)log V) = 500 × O((500+E)log 500)
              희소 그래프(E=500): 500 × 500×9 ≈ 2,250,000
              밀집 그래프(E=250,000): 500 × 250,000×9 ≈ 1.1억
→ 밀집 그래프: 플로이드-워샬과 유사, 희소: 다익스트라×V가 유리

📢 섹션 요약 비유: 플로이드-워샬과 다익스트라의 선택은 전국 도로 지도를 한 번에 완성하느냐(전체 쌍), 특정 도시에서 출발하는 지도만 그리느냐의 차이다.

Ⅳ. 실무 적용 및 기술사 판단

실무 시나리오

시나리오 1: 도시 간 운송 비용 최적화 (물류)

• V=50개 창고 간 모든 쌍 최단 경로 사전 계산
• 플로이드-워샬 1회 실행 → 이후 모든 배송 경로 O(1) 조회

시나리오 2: 소셜 네트워크 친밀도 거리 계산

• 모든 사용자 쌍 간 최단 관계 거리
• V가 수천 이하 소규모 네트워크에서 활용

시나리오 3: 게임 NPC 이동 (소규모 격자)

• V=30×30=900 격자에서 모든 위치 간 이동 비용 사전 계산
• 900³ = 7.3억 → 허용 가능 (1회 전처리 후 O(1) 조회)

기술사 판단 포인트

📢 섹션 요약 비유: 플로이드-워샬은 항공사가 모든 도시 쌍 간 최단 환승 경로를 시즌 시작 전에 한 번에 계산해두는 것과 같다. 한 번의 큰 계산으로 이후 모든 질문에 즉시 답변한다.

Ⅴ. 기대효과 및 결론

플로이드-워샬 (Floyd-Warshall) 알고리즘은 V×V×V 3중 루프라는 단순한 구현으로 전체 쌍 최단 경로를 해결한다. 음수 간선 처리와 음수 사이클 검출이 가능하며, V ≤ 500 이하의 밀집 그래프에서 특히 효율적이다.

핵심 결론: "모든 쌍 최단 경로가 필요하고 그래프가 작다면 플로이드-워샬이 가장 단순하고 올바른 선택이다."

📢 섹션 요약 비유: 플로이드-워샬은 작은 마을 지도를 직접 발로 뛰어 만드는 방법이다. 마을이 작다면 이 방법이 가장 직관적이고 정확하지만, 마을이 서울만큼 커지면 무리다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[단일 출발 최단 경로(Dijkstra)]
    │
    ▼
[전체 쌍 최단 경로 문제]
    │
    ▼
[플로이드-워셜(DP 점화식)]
    │
    ▼
[음수 사이클 감지]
    │
    ▼
[네트워크 라우팅 응용]

플로이드-워셜은 모든 쌍 최단 경로를 동적 계획법으로 구하고 음수 사이클까지 탐지하는 알고리즘이다.

👶 어린이를 위한 3줄 비유 설명

1. 🏙️ 10개의 도시가 있을 때, "A에서 B로 가려면 C를 거치면 더 빠를까?"를 모든 도시 조합에 대해 확인하는 것이 플로이드-워샬이다.
2. 🔄 중간 거점 도시를 하나씩 추가해가며 지도를 업데이트하기 때문에, V개 도시를 V번 검토하면 모든 경로가 완성된다.
3. ⚠️ 자기 자신으로 돌아오는 경로가 음수라면 무한히 싼 경로가 존재한다는 뜻이므로, 그 경우는 알고리즘이 경고를 보낸다.