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

플로이드-워셜 알고리즘

"그래프에서 모든 노드 간 최단 경로를 한 번에 구하는 알고리즘"

• 음수 간선도 처리 가능 (음수 사이클은 처리 불가!)
• 모든 노드에서 모든 노드까지의 최단 경로를 한 번에 계산
• 동적 계획법(DP) 기반으로 O(V³)의 시간복잡도를 가짐
• 노드 개수가 작을 때 사용하기 적합

---

플로이드-워셜 알고리즘 동작 원리

1. 모든 노드 간의 최단 거리를 저장하는 2차원 DP 테이블(행렬) 초기화
2. 모든 노드를 '경유지(K)'로 설정하면서 최단 경로 갱신
3. 테이블이 더 이상 갱신되지 않으면 종료

# Pseudo Code
FUNCTION FloydWarshall(graph, V):
    거리 = 그래프의 가중치 행렬 초기화

    FOR k FROM 1 TO V DO:  # 모든 노드를 경유지로 설정
        FOR i FROM 1 TO V DO:
            FOR j FROM 1 TO V DO:
                거리[i][j] = min(거리[i][j], 거리[i][k] + 거리[k][j])

    RETURN 거리


# Full Code
INF = float('inf')

def floyd_warshall(graph, V):
    # 거리 행렬 초기화
    dist = [[INF] * V for _ in range(V)]
    
    for i in range(V):
        dist[i][i] = 0  # 자기 자신으로 가는 거리는 0
    
    # 초기 그래프 값 복사
    for u in range(V):
        for v, weight in graph[u]:
            dist[u][v] = weight  # 직접 연결된 경로 입력

    # 플로이드-워셜 알고리즘 실행
    for k in range(V):  # 중간 노드
        for i in range(V):  # 시작 노드
            for j in range(V):  # 도착 노드
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist  # 최단 거리 행렬 반환

# 그래프 정의 (인접 리스트)
graph = {
    0: [(1, 4), (2, 3)],
    1: [(2, -1), (3, 2)],
    2: [(3, 5)],
    3: []
}

V = len(graph)
shortest_paths = floyd_warshall(graph, V)

# 결과 출력
for row in shortest_paths:
    print(row)

---

플로이드-워셜 알고리즘의 시간복잡도

경우	시간복잡도
모든 노드에서 모든 노드까지 계산	O(V³)

 

✅ 노드 개수(V)가 작을 때는 효율적이지만, V가 클 경우 매우 느려짐
✅ 간선 개수(E)와 관계없이 모든 노드 쌍을 고려하므로 희소 그래프에는 비효율적

---

플로이드-워셜 알고리즘의 장단점

장점

 

• 모든 노드 간 최단 경로를 한 번에 계산 가능
• 음수 가중치도 처리 가능 (음수 사이클은 감지 가능하지만 해결 불가!)
• 구현이 간단하고 직관적 (3중 반복문 사용)

단점

 

• 시간복잡도가 O(V³)라서 노드 개수가 크면 비효율적
• 음수 사이클이 있을 경우 올바른 최단 경로를 찾을 수 없음
• V가 크면 다익스트라를 여러 번 돌리는 방식이 더 효율적

결론

플로이드-워셜 알고리즘은 모든 노드에서 모든 노드까지 최단 거리를 구할 때 유용하지만, O(V³)의 시간복잡도로 인해 V가 크면 다익스트라를 여러 번 돌리는 방식이 더 효율적이다.