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

플로이드워셜 알고리즘은 각 정점에서 다른 모든 정점까지의 최단경로를 구할 수 있는 알고리즘이다.

기본적인 아이디어는 노드 A에서 노드 B로 이동에 필요한 비용과 노드 T를 경유하는 즉 노드 A -> 노드 T -> 노드 B 순으로 이동했을 때의 비용을 비교하여 노드 T를 경유한 경우의 비용이 작으면 A -> B 이동 비용을 작은 값으로 변경하는 것이다.

 

 

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

cost(A, B)를 노드 A에서 노드 B로 이동하는 비용 이라 하고

T를 경유하는 노드라 할 때

cost(A, B) = min(cost(A, B), cost(A, T) + cost(T, B))

 

플로이드워셜 알고리즘의 시간복잡도

노드의 개수를 N이라 할 때, 1 ~ N 노드는 모두 경유 노드가 될 수 있다.

경유 노드를 제외한 (N - 1)개의 노드는 각각 시작 노드가 된다.

(N - 1)개의 노드 중 시작 노드를 제외한 나머지 노드들이 도착 노드가 된다. 즉, (N - 1)개의 노드 중 임의의 두 노드를 나열하는 개수만큼의 비교 연산이 필요하다. 이는 순열의 개념이므로 (N - 1) P 2 로 계산할 수 있고 그 결과는 (N - 1)! / {(N - 1) - 2}! 이다. 이 것은 O(n^2) 시간 복잡도라 볼 수 있다. 

O(n^2)에 해당하는 시간복잡도의 연산을 각각의 경유 노드마다 반복해야 하므로 플로이드워셜 알고리즘의 시간복잡도는 O(n^3)이 된다.

 

플로이드워셜 알고리즘의 구현

import sys

fast_input = sys.stdin.readline
node_count, edge_count = map(int, fast_input().rstrip().split())
INF = int(1e9)

# Initialize Lowest Cost Table
graph = [[INF] * (node_count + 1) for _ in range(node_count + 1)]
lct = [[INF] * (node_count + 1) for _ in range(node_count + 1)]
for i in range(node_count + 1):
    graph[i][i] = 0
    lct[i][i] = 0
for _ in range(edge_count):
    i, j, cost = map(int, fast_input().rstrip().split())
    graph[i][j] = cost
    lct[i][j] = cost
    

def floyd_warshall(g):
    # T: 경유노드(transit node)
    for T in range(1, node_count + 1):
        # S: 시작노드(start node)
        for S in range(1, node_count + 1):
            if S == T:
                continue
            # A: 도착노드(arrival node)
            for A in range(1, node_count + 1):
                if S == A:
                    continue
                if lct[S][A] > lct[S][T] + lct[T][A]:
                    lct[S][A] = lct[S][T] + lct[T][A]


floyd_warshall(graph)
for i in range(1, len(lct)):
    for j in range(1, len(lct[i])):
        if lct[i][j] == INF:
            print('I', end= ' ')
        else:
            print(lct[i][j], end=' ')
    print()