최단경로 - 플로이드 워셜 알고리즘

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

다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘입니다.
 
이번에 설명하는 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘입니다. 다이나믹 프로그래밍을 기반으로 하며, 특히 밀집 그래프(dense graph)에서 효과적입니다.
 
 

플로이드 워셜 알고리즘의 개념

 

초기화

먼저, 최단 거리를 저장할 테이블(2차원 배열)을 초기화합니다. 이 테이블의 각 항목  dist[i][j]는 정점 i에서 j로 가는 최단 거리를 나타냅니다. 자기 자신으로의 거리는 0으로, 직접 연결된 정점 사이의 거리는 해당 가중치로, 그렇지 않은 경우에는 무한대(또는 매우 큰 수)로 설정합니다.
 

반복계산

그 후, 각 정점을 한 번씩 거쳐 가는 모든 경로에 대해, 현재 알고 있는 최단 거리와 해당 정점을 거쳐 가는 거리를 비교하여, 더 짧은 거리로 테이블을 갱신합니다. 이 과정은 dist[i][j] > dist[i][k] + dist[k][j] 인 경우 dist[i][j]를  dist[i][k] + dist[k][j]로 갱신하는 것을 포함합니다.

거쳐가는 정점

이 알고리즘은 '거쳐 가는 정점'을 기준으로 합니다. 즉, k번째 단계에서는 정점 k를 거쳐 가는 모든 경로를 고려합니다. 이렇게 모든 정점을 거쳐 가는 경로를 고려함으로써, 알고리즘이 진행됨에 따라 점진적으로 최단 경로를 구하게 됩니다.

 

예시를 통한 이해

플로이드 워셜 알고리즘을 이해하기 쉽도록 간단한 예를 들어 설명해보겠습니다.
여기서는 A, B, C, D 네 개의 도시가 있다고 가정하고, 각 도시 간의 도로와 그 도로를 이용하는 데 드는 시간(가중치)이 주졌다고 생각해봅시다.
 
다음과 같은 연결 상태가 있다고 가정합니다

• A-B 간의 도로가 있고, 이용 시간은 5시간입니다.
• A-C 간에는 직접 도로가 없습니다.
• A-D 간의 도로가 있고, 이용 시간은 9시간입니다.
• B-C 간의 도로가 있고, 이용 시간은 1시간입니다.

이제, 모든 도시 쌍 간의 최단 이동 시간을 찾고 싶다고 가정합니다. 이를 위해 우선 각 도시 간의 이동 시간을 나타내는 표를 만듭니다. 직접 연결이 없는 경우는 무한대로 표시합니다.

   A   B   C   D
A  0   5  ∞   9
B  5   0   3  ∞
C  ∞   3   0   1
D  9  ∞   1   0

플로이드 워셜 알고리즘을 사용하여 이 표를 갱신해 갑니다. 
각 단계에서, 모든 도시 쌍(i, j)에 대해, 다른 도시 k를 거쳐 가는 경로가 더 빠른지 확인합니다. 
즉, dist[ i ][ j ] 가 dist[ i ][ k ] + dist[ k ][ j ] 보다 큰지 비교합니다. 만약 그렇다면, dist[ i ][ j ]를 새로운 더 짧은 경로 값으로 갱신합니다.
 

1단계

B에서 D로 가는 직접 경로는 없지만, A를 거쳐서 가면 5+9 = 14시간이 됩니다. 현재 B-D 간의 경로가 무한이므로 14로 갱신합니다.

   A   B   C   D
A  0   5  ∞   9
B  5   0   3  14
C  ∞   3   0   1
D  9  ∞   1   0

 

2단계

A에서 C로 가는 직접 경로는 없지만, B를 거쳐서 가면 5 + 3 = 8시간이 걸립니다. 현재 A-C간의 경로가 무한이므로 8로 갱신합니다.

   A   B   C   D
A  0   5   8   9
B  5   0   3  14
C  ∞   3   0   1
D  9  ∞   1   0

이런 식으로 모든 도시를 거쳐 가는 모든 경로에 대해 검토하고 테이블을 갱신합니다.
각 도시를 중간경로로 사용하는 과정을 모든 도시에 대해 반복하면, 최종적으로 모든 도시 쌍 간의 최단 이동 시간을 얻을 수 있습니다.
 
이렇게 해서 완성된 표는 모든 도시 쌍 간의 최단 이동시간을 나타냅니다. 이 표를 이용하면 어떤 두 도시 간의 이동도 최적의 경로를 통해 이루어질 수 있습니다. 이 알고리즘의 핵심은 모든 가능한 경로를 고려한다는 것이며, 이를 통해 최단 경로의 글로 최적화를 달성할 수 있습니다.
 

시간 복잡도

플로이드 워셜 알고리즘은 모든 정점 쌍에 대해 최단 거리를 계산해야 하므로, 시간 복잡도는 O(V^3)입니다(`V`는 정점의 수). 공간 복잡도는 거리를 저장하는 2차원 배열에 의해 O(V^2)입니다.

플로이드 워셜의 장단점

 

장점

모든 정점 쌍 사이의 최단 거리를 한 번에 계산할 수 있고, 구현이 간단합니다. 또한 음수 가중치가 있는 그래프에서도 사용할 수 있습니다.
 

단점

그래프에 음수 순환(가중치의 합이 음수인 순환 경로)이 있는 경우, 알고리즘은 이를 처리할 수 없으며, 그래프가 클 때 시간 복잡도가 높습니다.
 

예시를 코드로 짠다면?

# 플로이드 워셜 알고리즘의 파이썬 구현 예시입니다.

# 무한대를 의미하는 값으로 정의합니다. 실제 구현에서는 적절한 큰 수를 사용할 수 있습니다.
INF = float('inf')

# 주어진 그래프의 인접 행렬을 초기화합니다.
# 예시 그래프는 위의 예시 설명에서 사용된 그래프와 동일합니다.
graph = [
    [0, 5, INF, 9],
    [5, 0, 3, INF],
    [INF, 3, 0, 1],
    [9, INF, 1, 0]
]

# 정점의 개수
n = len(graph)

# 플로이드 워셜 알고리즘을 수행합니다.
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 row in graph:
    print(row)

플로이드 워셜 알고리즘에서 `k`는 경유하는 노드(Intermediate node)를 나타냅니다.
 
알고리즘은 모든 노드 쌍 간의 최단 경로를 찾는 것이 목표인데, 이를 위해서는 경유하는 노드를 지정하는 것이 필요합니다.

주어진 코드에서 for k in range(n): 루프는 경유 노드 `k`를 0부터 `n-1`까지 순회하면서 최단 경로를 계산하는 역할을 합니다. 이렇게 `k`를 변경하면서 모든 노드 쌍 간의 최단 경로가 갱신됩니다.

알고리즘의 핵심 아이디어는 k 를 경유하는 경우와 경유하지 않는 경우를 비교하여 더 짧은 경로를 찾는 것이며, 이를 통해 모든 노드 쌍 간의 최단 경로를 계산할 수 있습니다.
 
 

또 다른 예시 코드

def floyd_warshall(graph):
    # 그래프의 크기 (정점의 개수)
    V = len(graph)
    
    # 결과를 저장할 2차원 배열 초기화
    dist = [[float('inf')] * V for _ in range(V)]

    # 자기 자신으로의 거리는 0으로 초기화
    for i in range(V):
        dist[i][i] = 0

    # 그래프의 간선 정보로 초기화
    for u in range(V):
        for v in range(V):
            if graph[u][v] != 0:
                dist[u][v] = graph[u][v]

    # 모든 정점 쌍에 대한 최단 경로 계산
    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, 3, 0, 0, 0, 0],
    [0, 0, 2, 0, 0, 0],
    [0, 0, 0, 7, 1, 0],
    [0, 0, 0, 0, 0, 4],
    [0, 0, 0, 2, 0, 5],
    [0, 0, 0, 0, 0, 0]
]

result = floyd_warshall(graph)

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