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

로봇공학을 공부하다가 알고리즘 파트가 나와서 공부해볼 겸 정리를 해본다.

pdf에는 단순히 DP를 이용한 최단거리 탐색 이라고 적혀 있지만, 사실상 플로이드 워셜 알고리즘을 설명하고 있다.

최단 거리를 찾는 알고리즘의 일종이다.

 

"거쳐가는 정점을 기준으로 최단거리를 구하는 것"

 

DP를 이용한다.

 

 

출처: https://blog.naver.com/ndb796/221234427842

이러한 그래프의 방문의 최적 비용을 2차원 테이블로 표현해 보자.

출처: https://blog.naver.com/ndb796/221234427842

이는 현재까지 계산된 최소비용이다.

2열 3행은 2-> 3으로 가는 현재까지 계산된 최소비용이고, 이는 9이다.

무한으로 표시된 것은 한 번의 이동으로는 갈 수 없는 즉, 필연적으로 다른 노드를 거쳐야 하는 경우이다.(만약 연결된 노드가 없는 경우 못 갈 수도 있다.)

 

예를 들어 1->3으로 가는 경우는 1 -> 4 -> 3을 거쳐서 비용 11, 1 -> 2 -> 3을 거쳐서 비용 14로 가는 방법이 있다.

첫 번째의 경우가 더 비용이 적기 때문에 현재까지 계산된 최소 비용을 바꿔준다.

이는 3중 반복문을 통해서 구현 가능하다. 따라서 시간 복잡도도 O(n^3)이다. 

 

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

arr = [[float('INF') for _ in range(n)] for _ in range(n)]
bus = []

for i in range(n):
    arr[i][i] = 0

for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    if arr[a-1][b-1] > c:
        arr[a-1][b-1] = c

#플로이드 와샬 알고리즘
for k in range(n):
    for i in range(n):
        for j in range(n):
            if arr[i][j] > arr[i][k] + arr[k][j]:
                arr[i][j] = arr[i][k] + arr[k][j]

for i in arr:
    print(*i)

3중 반복문 부분이 해당 알고리즘의 핵심인데 각각의 숫자를 넣어 그림을 그려보면 이해가 수월하다.

결론적으로 모든 조합을 다 찾아보는 것이다.