플로이드–워셜 알고리즘 (모든 노드 간 최단 경로 구하기)

문제 정의: 출발점이 고정되지 않은 최단경로 탐색

앞선 다익스트라와 벨만-포드는 모두

“특정 시작점에서 다른 모든 노드까지의 거리”를 구하는 알고리즘입니다.

하지만 실전에서는 이런 상황도 자주 생깁니다:

• A → B 최단거리?
• 모든 도시 쌍 간의 최소 소요 시간은?
• 특정 노드에서 어떤 노드로 거쳐 갈 때 경로는 어떤가?

이렇게 모든 정점 쌍 (i, j)에 대해 최단 거리를 구해야 하는 경우,
플로이드–워셜 알고리즘이 가장 효과적입니다.

---

개념 요약: 경유지를 하나씩 늘려가며 최단 거리 갱신

플로이드–워셜 알고리즘은

"한 노드에서 다른 노드로 갈 때, 어떤 노드를 거치면 더 짧아질 수 있을까?"
를 매 반복마다 전체 쌍에 대해 확인합니다.

이 알고리즘의 핵심은 **DP 테이블(2차원 배열)**을 쓰는 것입니다.

---

핵심 아이디어:

모든 노드 쌍 (i, j)에 대해,

경유 노드 k를 거쳤을 때
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

즉,

"기존 거리와 k를 경유했을 때 거리 중 더 짧은 쪽으로 갱신"
→ 이 연산을 k = 1부터 n까지 반복합니다.

---

알고리즘 동작 원리 단계별 설명

초기 세팅

• 노드 수: n
• dist[i][j] 테이블을 생성 (초기값: 간선 가중치, 연결 없으면 무한대)
• 자기 자신 dist[i][i] = 0

3중 반복 구조

for k in range(1, n+1):        # 경유지
    for i in range(1, n+1):    # 출발지
        for j in range(1, n+1):# 도착지
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

이 구조는 “점진적 최적화”라는 관점에서 이해하면 쉽습니다.

경로가 "점점 똑똑해지는 과정"이라고 보면 됩니다.

 

---

Python 구현 예제

def floyd_warshall(n, edges):
    INF = float('inf')
    dist = [[INF] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        dist[i][i] = 0

    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # 중복 간선 고려

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

 

edges = [
    (1, 2, 4),
    (1, 3, 2),
    (2, 3, 5),
    (3, 2, 1),
    (2, 4, 2),
    (3, 4, 3)
]

간선 입력 예

---

시간복잡도

단계	복잡도
테이블 초기화	O(V²)
3중 반복문	O(V³)

 

모든 정점 쌍에 대해 계산하므로
노드 수가 100 이하일 때 실용적,
→ 매우 작은 그래프에서는 가장 단순하면서도 강력한 최단경로 알고리즘

---

음수 간선 허용? 사이클은?

항목	지원 여부
음수 가중치	가능
음수 사이클 탐지	가능 (자기 자신으로 돌아오는 경우 확인)

 

 

---

다익스트라 / 벨만–포드 / 플로이드–워셜 비교

항목	다익스트라	벨만–포드	플로이드–워셜
지원	음수 X	음수 O	음수 O
사이클 탐지	X	O	O
시간복잡도	O(E log V)	O(VE)	O(V³)
목적	한 지점 → 모든 지점	한 지점 → 모든 지점 (음수 포함)	모든 지점 쌍 간 최단 거리

 

---

요약

• 플로이드–워셜은 그래프 내 모든 노드 쌍에 대한 최단 거리를 계산한다.
• 간단하지만 강력한 알고리즘으로, DP적 사고가 핵심
• 시간복잡도는 O(V³)로 다소 무겁지만, 작은 그래프에서는 매우 적합
• 음수 간선/음수 사이클까지 안전하게 처리 가능
• 전체 경로 테이블이 필요할 때는 이게 최적의 선택!