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

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

Created
2022/07/10
Tags
Algorithm
Floyd-Warshall
 
2022-07-10 @이영훈
 
플로이드-워셜 알고리즘을 기록으로 남깁니다.
 
나동빈님의 유튜브 영상을 보며 공부하였습니다.
 
 

플로이드-워셜 알고리즘 설명

notion image
 
 
플로이드-워셜 알고리즘은 a → b로 가는 비용과 a → k → b로 가는 비용 중 더 적은 것을 최단 거리로 설정합니다. 그래서 다음과 같은 점화식을 만들 수 있습니다
notion image
 
 

동작 과정

행(row)은 출발점, 열(column)은 도착점인 2차원 행렬을 만듭니다.
그리고 a → b로 가는 경로의 초기 비용을 설정합니다.
notion image
 
 
그리고 1번 노드를 거쳐 가는 경우에 min(a → b, a → 1 → b)를 계산하여 행렬을 갱신합니다.
a → 1 → b로 가는 경우는 1번 노드 자기 자신을 제외한 총 3개의 노드에서 3 x 2 = 6가지 입니다.
그래서 2차원 행렬에서 파란색으로 표시된 갱신 가능한 부분은 6군데 입니다.
예를 들어, 3번 → 1번 → 2번 노드로 가는 비용은 5 + 4 = 9 입니다. 3번 → 2번 노드로 바로 가는 경우는 없기(무한) 때문에 9로 업데이트 되었습니다.
notion image
 
 
이 과정을 반복하여 이번에는 2번 노드를 거쳐 가는 경우에도 행렬을 업데이트 합니다.
notion image
 
 
3번 노드를 거쳐 가는 경우의 행렬 업데이트 과정을 진행합니다.
notion image
 
 
4번 노드를 거쳐 가는 경우의 행렬 업데이트 과정을 진행합니다.
notion image
 
 

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

이 과정을 보면 대략적인 알고리즘 흐름을 알 수 있습니다.
Python
# 전체적인 과정
(for문) k번 노드를 거쳐 가는 과정
	min(a → b, a → k → b)

# 여기에서 min(a → b, a → k → b)을 계산할 때 2차원 행렬이기 때문에 2중 반복문을 사용하게 됩니다.

# 풀어쓴 전체적인 과정
(for문) k번 노드를 거쳐 가는 과정
	(for문) 행(row) 탐색
		(for문) 열(column) 탐색
			min(row -> column, row -> k -> column) 	
 
따라서 플로이드-워셜 알고리즘의 시간복잡도는 O(n^3) 입니다
 
최단거리 문제가 출제되었을 때 다익스트라, 플로이드-워셜 등의 알고리즘 중에서 어떤 것이 더 적절한 지 판단해야 합니다.
  • 플로이드-워셜로 N이 500인 문제를 푼다고 가정했을 때, 500 * 500 * 500 > 1.2억이 넘어가기 때문에 느립니다. 시간 초과가 날 수 있습니다.
 
notion image
 
 
 

파이썬 코드로 구현

Python
INF = int(1e9)  # 무한을 10억으로 설정

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

# 2차원 리스트(그래프)를 만들고 무한으로 초기화
graph = [[INF] * (1 + n) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for i in range(1, n + 1):
    graph[i][i] = 0

# 각 간선에 대한 정보를 받아 그 값으로 초기화
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n + 1):  # k를 거쳐 가는 경우
    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):
        # 도달할 수 없는 경우, 무한(INF)으로 출력
        if graph[a][b] == INF:
            print("INF", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()