플로이드 워셜(Floyd-Warshall) 알고리즘이란 무엇인가?

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

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 구하고자 할 때 사용하는 알고리즘입니다.
• 다익스트라 알고리즘과 마찬가지로 거쳐 가는 노드를 기준으로 알고리즘을 수행합니다.
• 2차원 테이블에 최단 거리 정보를 저장합니다.
• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속합니다.
• $O(N^3)$의 시간복잡도를 가집니다.

플로이드 워셜 알고리즘의 점화식

• 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인합니다.
• $D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

플로이드 워셜 알고리즘 동작 방식

[출처 : https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7]

1. 각 노드에서 갈 수 있는 노드에 대한 거리를 2차원 테이블에 초기화합니다.
2. 각 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신합니다.
   • 1번 노드를 거쳐가는 경우 -> $D_{ab} = min(D_{ab}, D_{a1} + D_{1b})$
   • 2번 노드를 거쳐가는 경우 -> $D_{ab} = min(D_{ab}, D_{a2} + D_{2b})$
   • 3번 노드를 거쳐가는 경우 -> $D_{ab} = min(D_{ab}, D_{a3} + D_{3b})$
   • 4번 노드를 거쳐가는 경우 -> $D_{ab} = min(D_{ab}, D_{a4} + D_{4b})$
   • 5번 노드를 거쳐가는 경우 -> $D_{ab} = min(D_{ab}, D_{a5} + D_{5b})$
   • 6번 노드를 거쳐가는 경우 -> $D_{ab} = min(D_{ab}, D_{a6} + D_{6b})$

[코드]

n = int(input())
m = int(input())
INF = int(1e9)

# 2차원 테이블 생성 및 INF로 초기화
floyd_table = [[INF]*(n+1) for _ in range(n+1)]

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

# 입력받은 값으로 초기화
for _ in range(m):
    # a에서 b로 가는 비용이 c
    a, b, c = map(int, input().split())
    floyd_table[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘 수행
def floyd_warshall():
    for k in range(1, n+1):
        for a in range(1, n+1):
            for b in range(1, n+1):
                # a : 출발노드, k : 거쳐가는 노드, b : 도착노드
                floyd_table[a][b] = min(floyd_table[a][b], floyd_table[a][k] + floyd_table[k][b])

floyd_warshall()
for a in range(1, n+1):
    for b in range(1, n+1):
        if floyd_table[a][b]==INF:
            print('0', end=' ')
        else:
            print(floyd_table[a][b], end=' ')
    print()

플로이드 워셜 알고리즘의 성능

• 노드의 개수가 N개 일 때, 알고리즘상으로 N번의 단계를 수행합니다.
  - 각 단계마다 $O(N^2)$의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려합니다.
• 그렇기에 플로이드워셜 알고리즘의 시간복잡도는 $O(N^3)$이 됩니다.
• 노드의 개수가 500개 이하일 때 사용가능한 알고리즘 입니다.