[WEEK03] 플로이드-워셜 알고리즘

플로이드-워셜 알고리즘

플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점 간의 최단 경로를 찾는 알고리즘이다. 다익스트라(Dijkstra) 알고리즘이 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 방식이라면, 플로이드-워셜은 모든 정점에서 모든 정점까지의 최단 경로를 구하는 방식이다.

 

이 알고리즘은 동적 계획법(DP, Dynamic Programming)을 활용하여 최단 거리를 점진적으로 갱신하는 방식으로 동작한다.

알고리즘 원리

플로이드-워셜 알고리즘의 핵심 아이디어는 점진적인 경로 갱신이다. 즉, 현재 고려하는 정점을 경유지로 삼았을 때 경로가 더 짧아질 수 있는지 확인하는 방식으로 동작한다.

1. 그래프를 인접 행렬(Adjacent Matrix) 형태로 표현한다.
2. 모든 정점 쌍 (i, j)에 대해 직접 연결된 거리를 초기화한다.
3. 모든 정점 k를 중간 정점으로 고려하여 최단 경로를 갱신한다.
   • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
4. 이 과정을 모든 노드에 대해 반복하면 최단 거리 행렬이 완성된다.

알고리즘 구현

다음은 플로이드-워셜 알고리즘을 파이썬으로 구현한 코드이다.

INF = float('inf')

def floyd_warshall(graph):
    num_vertices = len(graph)
    dist = [row[:] for row in graph]  # 거리 행렬 초기화
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

# 예제 그래프 (인접 행렬 형태)
graph = [
    [0, 3, INF, INF],
    [2, 0, INF, INF],
    [INF, 7, 0, 1],
    [6, INF, INF, 0]
]

shortest_paths = floyd_warshall(graph)
for row in shortest_paths:
    print(row)

시간 복잡도

플로이드-워셜 알고리즘의 시간 복잡도는 O(V³) 이다.

• 세 개의 중첩된 반복문이 각각 V(정점의 개수) 만큼 실행되므로 O(V³) 이다.
• 따라서 정점의 개수가 클 경우(예: 1000개 이상)에는 다익스트라 알고리즘 등을 고려하는 것이 좋다.

플로이드-워셜 알고리즘의 활용

• 네트워크 지연 시간 분석
• 도시 간 최단 거리 계산
• 게임 맵의 모든 지점 간 이동 경로 계산
• GPS 네비게이션 시스템의 기초

정리

플로이드-워셜 알고리즘은 모든 정점 간의 최단 경로를 효율적으로 구할 수 있는 강력한 알고리즘이다. 특히, 그래프가 작을 경우 매우 직관적이고 쉬운 구현이 가능하므로 알고리즘 문제를 풀 때 유용하게 활용할 수 있다.

---

같이 보면 좋을 자료들

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

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

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

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

• 그래프 알고리즘 한눈에 훑기

그래프 알고리즘 한눈에 훑기