플로이드 워셜 알고리즘[파이썬 예제 코드]

플로이드 워셜 알고리즘은 다익스트라, 벨만-포드 알고리즘과 같은 최단 경로 알고리즘이다.

단, 다익스트라와 벨만-포드 알고리즘이 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는데 사용되었다면 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점 까지의 최단 경로를 모두 구해야 하는 경우에 사용 가능하다.

이 외에도 다른 최단 경로 알고리즘과 플로이드 워셜 알고리즘의 차이점에는 여러가지가 있다.

다익스트라의 경우 최단 거리를 저장하기 위해 1차원 배열을 사용하였지만 플로이드 워셜의 경우 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 저장해야 하기 때문에 2차원 배열에 최단 거리 정보를 저장한다.

또한 다익스트라가 그리디 알고리즘이었던것에 반해, 플로이드 워셜은 DP이다.

N개의 노드가 존재할 때, N번 만큼 반복하여 점화식에 맞게 2차원 배열을 갱신한다.

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

플로이드 워셜의 기본 개념은 다음과 같다.

👉  바로 이동하는 거리가 특정 노드를 거쳐서 이동하는 거리보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신한다.

Dab = min$($Dab, Dak + Dkb)

위 점화식은 a에서 b로 가는 최소비용과 a에서 k를 거쳐 b로 가는 비용을 비교하여 더 작은 값으로 갱신한다.

N개의 노드가 있을때, a에서 b로 1 ~ N개의 노드를 거쳐가는 모든 경우를 구한 다음 거쳐가는 비용과 바로 가는 비용 중 더 작은 값으로 업데이트 한다.

플로이드 워셜 알고리즘 수행과정

4개의 노드$($1 ~ 4)가 존재한다고 가정하고 플로이드 워셜 알고리즘의 수행 과정을 살펴보도록 하겠다.

먼저 1번 노드를 거쳐 가는 경우를 계산해 보겠다.

1번 노드를 제외한 2, 3, 4번 노드에서 2개의 노드를 뽑는 경우를 고려한다.

$($2, 3), $($2, 4), $($3, 2), $($3, 4), $($4, 2), $($4, 4)

먼저 D23, $($2, 3)의 경우 , 2번 노드에서 3번 노드로 바로 가는 비용과 2에서 1번 노드를 거쳐서 3으로 가는 비용 중, 더 작은 값으로 Graph[2][3]값을 갱신한다.

D23 = min$($D23, D21 + D13)

나머지 5개 값도 1번 노드를 거쳐가는 경우와 바로가는 경우를 비교하여 더 작은 값으로 2차원 배열 값을 갱신한다.

마찬가지로 2번 노드를 거쳐가는 경우를 계산한다.

2번 노드를 제외한 1, 3, 4번 노드에서 2개의 노드를 뽑는 경우를 고려한다.

$($1, 3), $($1, 4), $($3, 1), $($3, 4), $($4, 1), $($4, 3)

D13의 경우 원래 무한대의 값을 가졌기 때문에 D12 + D23 = 11로 갱신한다.

3번노드를 거쳐가는 경우, 4번 노드를 거쳐가는 경우도 같은 방식으로 진행하여 2차원 배열을 업데이트 해준다.

노드의 개수만큼 위의 과정을 반복하고 나면 2차원 배열에는 모든 노드에서 모든 노드로 가는 최단 거리 정보가 저장된다.

최종결과

예를 들어 D14의 경우 1번 노드에서 3번 노드로 가는 최단 거리가 6이라는 것을 알 수 있다.

플로이드 워셜 알고리즘 코드 (Python)

INF = int(1e9)

# 노드의 개수 v, 간선의 개수 e 입력받기
v, e = map(int, input().split())
# 모든 노드에서 모든 노드로 가는 최단 거리 저장을 위한 2차원 배열 생성
# 초기값은 무한대로 초기화
G = [[INF] * (v + 1) for _ in range(v + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, v + 1):
    for b in range(1, v + 1):
        if a == b:
            G[a][b] = 0

# 각 간선에 대한 정보 입력
for _ in range(e):
    # a에서 b로 가는 비용 c
    a, b, c = map(int, input().split())
    G[a][b] = min(G[a][b], c)
    
# 점화식에 따라 플로이드 워셜 알고리즘 수행 
for k in range(1, v + 1):
    for a in range(1, v + 1):
        for b in range(1, v + 1):
            G[a][b] = min(G[a][b], G[a][k] + G[k][b])
            
# 모든 노드에서 모든 노드로 가는 최단 경로 출력
for a in range(1, v + 1):
    for b in range(1, n + 1):
        # 도달할 수 없는 경우, INFINITY 출력
        if G[a][b] == INF: print("INFINITY", end=" ")
        # 도달할 수 있는 경우, 거리를 출력
        else: print(G[a][b], end=" ")
    print()

시간복잡도

앞서 설명했듯이 2차원 배열에 최단 거리 정보를 저장한다.

현재 확인하고 있는 노드를 제외하고, N - 1개의 노드 중에서 서로 다른 노드 $($A, B)쌍을 선택한다.

그 다음 A에서 1번노드를 거쳐 B로 가는 경로가 존재한다면 A → 1번 노드 → B로 가는 비용을 확인한 다음 최단 거리를 갱신단다. 때문에 O$($N²)시간이 걸리고, 노드의 단계별로 N번 2차원 배열을 처리해야 하기 때문에 O$($N³) 의 시간이 소요된다.

최단 경로를 찾아야 하는 문제를 마주한 경우, 노드의 개수가 많지 않다면 플로이드-와샬 알고리즘을 적용해도 좋다.

하지만 노드와 간선의 개수가 많다면, 우선 순위큐를 이용한 다익스트라 알고리즘을 사용하는 편이 유리하다는 것을 주의하자.