[algorithm] 플로이드-워셜 (Floyd-Warshall) 알고리즘

🧐 플로이드-워셜 알고리즘: 모든 노드 간 최단 경로 찾기

 

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

플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프의 모든 노드 쌍 간 최단 경로를 찾는 알고리즘입니다.

동적 프로그래밍(Dynamic Programming) 기법을 사용하며, 다익스트라와 다르게 음수 가중치가 있는 그래프도 처리할 수 있다는 장점이 있습니다.

 

2. 알고리즘의 동작 원리

이 알고리즘은 특정한 경유지 노드(k)를 거쳐 가는 경우와 바로 가는 경우를 비교하며 최단 경로를 갱신합니다.

점화식:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

dist[i][j]: 노드 i에서 노드 j로 가는 현재까지의 최단 거리
k: 경유하는 노드

 

3. 알고리즘 구현

INF = float('inf')

# 그래프 초기화 (노드 개수 n)
n = 4
graph = [[0, 5, INF, 8],
         [7, 0, 9, INF],
         [2, INF, 0, 4],
         [INF, INF, 3, 0]]

# 플로이드-워셜 알고리즘
for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 결과 출력
for line in graph:
    print(line)

 

4. 시간 복잡도와 특징

• 시간 복잡도: O(n^3)
• 공간 복잡도: O(n^2)
• 음수 가중치 처리 가능 (단, 음수 사이클이 있는 경우는 불가)

 

5. 활용 예시

• 모든 도시 간 최단 거리 계산
• 네트워크에서 모든 노드 간 최소 지연 시간 찾기

 

6. 배운점

플로이드-워셜 알고리즘은 구현이 간단하고 모든 노드 간 최단 경로를 효율적으로 구할 수 있습니다.

특히 노드 개수가 많지 않은 경우 유용하며, 다익스트라 알고리즘과 함께 최단 경로 문제에서 자주 사용됩니다.