플로이드-워셜 알고리즘 / 백준 11404번 플로이드 Python

'다익스트라 알고리즘'은 매우 친숙하지만, '플로이드-워셜' 알고리즘은 처음 들어봐서 이 글을 작성하게 되었다. 

 

다익스트라는 하나의 정점에서 다른 정점까지 최단거리만 구해주는데, 플로이드-워셜은 모든 노드간 최단 경로를 구할 수 있다. 

 

이 알고리즘의 핵심은 모든 노드를 중간으로 해서 나오는 값으로 업데이트를 해주는 과정이다. 

 

 

이런 그래프가 있다고 해 보자.

 

이렇게 거리 배열을 만들었다. 

 

그리고, 1번 노드를 새로운 중간노드로 설정해서 값을 업데이트 해준다. 

 

 

 

2번 노드를 새로운 중간노드로 설정해서 값을 업데이트 해준다.

 

 

 

이렇게 5번까지 해줘야 한다...

시간복잡도는 O(n^3)이라서 n이 작을때만 써야한다!!

 

 각 노드별 모든 거리를 살펴보면서 k를 중간 노드로 삼을 때와 아닐 때의 값을 비교해 더 작은 값으로 업데이트 하는 식으로 코드를 짜면 된다. 끝!

 

참고: chanhuiseok.github.io/posts/algo-50/ 갓 블로그..

 

 

[코드] 이자 백준 11404번 풀이

# 11404번 플로이드
import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
data = [[sys.maxsize] * (n + 1) for _ in range(n + 1)]

for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    data[a][b] = min(c, data[a][b])

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            data[i][j] = 0

# update
for midValue in range(1, n+1):  # 중간값
    for i in range(1, n+1):  # 테이블 안에 도는 용도
        for j in range(1, n+1):
            data[i][j] = min(data[i][midValue] + data[midValue][j], data[i][j])

for i in range(1, n+1):
    for j in range(1, n+1):
        if data[i][j] == sys.maxsize:
            data[i][j] = 0
        print(f"{data[i][j]} ", end='')
    print("")

build in PyPy