Floyd-Warshall algorithm (플로이드-워셜)

# 정의

 

플로이드-워셜 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘입니다. 다익스트라 알고리즘과는 다르게 음의 가중치를 가진 간선이 있어도 처리할 수 있습니다.

이를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야한다. BFS를 설명할때 이미 했기 때문에 링크만 올려두겠습니다.

https://whitem4rk.tistory.com/18

BFS (Breadth First Search )

 

# Code

플로이드-워셜 알고리즘은 동적 계획법(Dynamic Programming)을 기반으로 하며, 아래와 같은 방법으로 구현됩니다.

1. 그래프의 인접 행렬을 D[0]으로 초기화합니다.
2. k를 1부터 N까지 증가시키면서, D[k]를 다음과 같이 갱신합니다.이때, D[k-1]은 이전 단계에서 구한 최단 경로를 나타내며, D[k]는 k를 거쳐가는 최단 경로를 나타냅니다.
3. D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])
4. k=N일 때의 D[N]이 모든 정점 쌍 간의 최단 경로를 나타냅니다.

쉽게말해서 1,2,3 노드가 삼각형으로 있을때 2번 노드를 기준으로 1 -> ★2★ -> 3 비용과 1 -> 3 비용중 작은것을 계속해서 갱신하는 방식이다.

아무래도 말로만 설명하면 이해가 어려울것 같아서 영상을 보고 이해하는것이 좋을것 같다.

https://www.youtube.com/watch?v=9574GHxCbKc 

 

가장 기본적인 파이썬 코드이다.

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 사용합니다.

def floyd_warshall(graph):
    n = len(graph)
    dist = [[INF] * n for _ in range(n)]
    
    # 인접 행렬을 D[0]으로 초기화합니다.
    for i in range(n):
        for j in range(n):
            dist[i][j] = graph[i][j]
    
    # k를 1부터 N까지 증가시키면서, D[k]를 갱신합니다.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

 

# 수행시간

알고리즘의 핵심은 모든 정점 쌍 간의 최단 경로를 구하는 것입니다. 따라서 n개의 정점이 있다면 이 작업을 수행하기 위해 n^2번의 연산이 필요합니다. 또한, k를 거쳐가는 최단 경로를 구하는 부분에서도 n^2번의 연산이 필요합니다. 이러한 과정을 k를 1부터 N까지 증가시키면서 수행하므로, 전체 연산 횟수는 O(n^3)입니다.

따라서 플로이드-워셜 알고리즘은 그래프의 크기가 작을 때에는 빠르게 동작하지만, 그래프의 크기가 커지면 다른 알고리즘을 사용하는 것이 좋습니다. 또한, 플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하는 것이 목적이기 때문에, 하나의 출발 정점에서 다른 모든 정점으로의 최단 경로를 구하는 문제에는 다익스트라 알고리즘이나 벨만-포드 알고리즘이 더 적합합니다.

 

# 실제 쓰임

1. 인터넷에서 각 노드가 서로 어떻게 연결되어 있는지, 각 노드 간의 최단 경로가 어떻게 되는지 등을 분석
2. 물류 업무에서 트럭이 여러 지점을 방문할 때, 모든 지점을 방문하는데 드는 최단 경로를 구할 때
3. 동적 계획법(Dynamic Programming)을 적용할 때, 부분 문제들 간의 의존성을 나타내는 그래프에서 최단 경로를 미리 계산해 놓으면 계산 속도를 향상시킬 수 있습니다.

 

 

# Reference

ChatGPT

https://www.youtube.com/watch?v=9574GHxCbKc