[코드조각] 플로이드-워셜

 플로이드-워셜 알고리즘은 그래프 간의 모든 정점에서 다른 정점까지의 최단거리를 쉽게 구하는 알고리즘이다.

 모든 정점과 정점 사이의 최단거리가 필요하거나, 키 비교, 줄 세우기 등의 문제에서 사용할 수 있다.

import math

N = int(input()) #정점의 개수
M = int(input()) #입력할 간선 정보의 개수

#정점과 정점사이의 거리. d[i][j]는 노드 i에서 노드 j까지의 거리
d = [[math.inf for i in range(N)] for j in range(N)]

#자기 자신부터 자기 자신의 거리가 0
for i in range(N):
	d[i][i] = 0

#간선 정보 입력
while M:
    # 출발지점, 끝지점, 비용
    S, E, C = map(int, input().split())    
    d[S][E] = min(d[S][E], C)

#플로이드-워셜
for m in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j] > d[i][m] + d[m][j]:
                d[i][j] = d[i][m] + d[m][j]:

for i in d:
    print(*i)

 최단거리를 구하는 방식은 초기에 모든 노드간 거리가 있는 배열을 생성하고, 노드A와 B의 거리보다, 노드A에서 M을 거쳐 B로 가는 것이 더 짧다면, 그것으로 거리를 갱신하는 것이다. 

 시간복잡도는 O(N^3)이다. 코드는 최단거리 구하기 중에서 제일 간단하지만, 시간복잡도가 매우높아 데이터가 적은 문제에서 유리하다.