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

Floyd-Warshall

Idea

플로이드-워셜 알고리즘은 모든 정점에서 다른 모던 정점까지의 최단 경로를 모두 구하는 알고리즘입니다. 모든 정점에서 다른 모든 정점까지의 최단 거리를 저장해야 하기 때문에 2차원 테이블에 최단 거리 정보를 저장합니다.

경로 계산 방식에는 아래와 같은 종류가 있습니다.

1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기
2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기
3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기

플로이드 워셜 알고리즘은 이 중 3번째 유형(All-To-All) 입니다.

플로이드 워셜 알고리즘의 점화식은 아래와 같습니다.

floyd-warshall algorithm

3중 반복문을 이용하여 위 점화식을 기준으로 테이블을 갱신시키는 것입니다.
위 점화식에 의해서  "a에서 b로 가는 최소 비용"과 "a에서 k를 거쳐 b로 가는 비용"을 비교하여 더 작은 값으로 갱신한다. 

매 단계마다 '현재 노드를 거쳐 가는 노드'를 기준으로 알고리즘을 수행합니다. 

 

또한, 초기 테이블 설정 시, "연결되지 않은 간선"에는 임의의 큰 값을 넣고, 자기 자신으로 가능 비용은 모두 0으로 초기화합니다. 그리고 현재 노드가 포함된 행과 열은 업데이트되지 않습니다.

 

동작 과정

[step 0] 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다.

 

[step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

 

[step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

 

[step ~] 3번, 4번, ... 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

 

Code

import sys

input = sys.stdin.readline
INF = int(1e9)

# 노드의 개수(n)과 간선의 개수(m) 입력
n = int(input())
m = int(input())

# 2차원 리스트 (그래프 표현) 만들고, 무한대로 초기화
graph = [[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:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(m):
    # A -> B로 가는 비용을 C라고 설정
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 수행된 결과를 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print('INFINITY', end=' ')
        else:
            print(graph[a][b], end=' ')
    print()

# sample input
# 4
# 7
# 1 2 4
# 1 4 6
# 2 1 3
# 2 3 7
# 3 1 5
# 3 4 4
# 4 3 2

 

 

Time Complexity

• 시간 복잡도:  O(N^3)
  노드의 개수가 N개 일 때, N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는 모든 경로'를 고려합니다. 따라서 시간 복잡도는 총 O(N^3)입니다.