[크래프톤 정글 5기] 플로이드 워셜 알고리즘 + 파이썬 구현

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

- 다익스트라가 특정 정점과 특정 정점까지의 최단 경로를 구하는 알고리즘 이라면, 플로이드 워셜은 모든 정점에서 다른 모든 정점까지의 최단 경로를 모두 찾는 탐색 알고리즘

- 다익스트라는 그리디, 플로이드 워셜은 DP

- 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N²)의 연산을 통해 ‘현재 노드를 거쳐 가는 모든 경로’를 고려한다. 따라서 총 시간 복잡도는 O(N³)이다.

 

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

1. 인접 행렬 방식으로 출발노드, 도착노드, 비용을 입력한다. 갈 수 없다면 INF로 설정한다.

2. k(거쳐갈 노드), a(출발 노드), b(도착 노드) 순서로 3중 for문을 만든다. a->b 비용과 (a->k) + (k->b) 비용 중 더 짧은 거리를 인접 행렬에 갱신한다.

 

점화식 ( k는 거쳐가는 노드, 모든 노드가 한 번씩 k가 된다 )

D_ab = min(D_ab, D_ak + D_kb)

a -> b의 최단거리 = a -> b로 가는 거리와, a -> k를 거쳐 k -> b로 가는 거리 중 짧은 거리를 선택

플로이드 워셜

 

 

플로이드 워셜2

 

해당 테이블에서 변경을 시도할 값이 선택되는 기준은, 현재 선택된 K값(거쳐갈 노드)에 해당하는 행과 열, 그리고 자기 자신에게 향하는 0값을 제외한 나머지이다.

 

 

 

플로이드 워셜 알고리즘 파이썬 연습 코드

import sys

input = sys.stdin.readline

INF = int(1e9)

n = int(input())

m = int(input())

graph = [[INF] * (n + 1) for _ in range(n + 1)]  # 노드번호와 인덱스를 맞추기 위해 n + 1, INF로 초기화

for a in range(1, n + 1): # 자기 자신을 향하는 경로는 0으로 초기화

    for b in range(1, n + 1):

        if a == b:

            graph[a][b] = 0

for _ in range(m):  # 간선 정보 입력받기

    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()

# 4

# 7

# 1 2 4

# 1 4 6

# 2 1 3

# 2 3 7

# 3 1 5

# 3 4 4

# 4 3 2

 

플로이드 워셜 알고리즘의 구현은 매우 쉽다. 딱 저 4줄이 끝이다.

점화식도 간결하고 외우기 좋다. 노드나 간선의 수가 적을 때 다익스트라 대신 플로이드 워셜 알고리즘을 사용하면 매우 편할 듯 하다.

 

맨 아래 주석은 테스트 케이스 입력값이다. 오타 없이 코딩했을 경우 결과는 이렇다.

0 4 8 6
3 0 7 9
5 9 0 4
7 11 2 0