알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 플로이드 워셜

08-6 플로이드-워셜

기능: 모든 노드 간에 최단 경로 탐색 (시작점 x)

특징

- 음수 가중치 에지가 있어도 수행할 수 있음 (음수 사이클은 있으면 안됨)

- 동적 계획법의 원리를 이용해서 알고리즘에 접근

시간 복잡도: O(v^3) -> 노드의 개수가 1000 이런식이면 쓰면 안됨

 

핵심 이론

A 노드에서 B 노드까지 최단 경로를 구했다면, 그 경로위에 K노드가 존재했을 때 그 부분 경로 역시 최단 거리임

전체의 최단 거리는 부분의 최단 거리의 합과 같음

D[s][e] = Math.min(D[s][e], D[s][k] + D[k][e]

 

1. 리스트를 선언하고 초기화하기

인접행렬로 선언 가능 (노드의 개수가 적을테니)

 

2. 최단 거리 리스트에 그래프 데이터 저장하기

 

3. 점화식으로 리스트 업데이트하기

점화식을 3중 for문의 형태로 반복

for 경유지 k에 관해 (1~N): # N는 노드의 개수
	for 출발 노드 s에 관해 (1~N):
    	for 도착 노드 e에 관해 (1~N):
        	D[s][e] = Math.min(D[s][k]+ D[k][e], D[s][e])

 

모든 쌍의 노드에 대한 최단거리 표현 (무한대는 갈 수 없는 거리)

 

코드

import sys
input = sys.stdin.readline

n = int(input())
v = int(input())

graph = [float('inf')] * (n+1) for _ in range(n+1)]

for _ in range(n):
	v1, v2, c = map(int, input().split())
    graph[v1][v2] = c

for i in range(1, n+1):
	graph[i][i] = 0
    
for k in range(1, n+1): # 경유할 점
	for i in range(1, n+1):
    	for j in range(1, n+1):
        	graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])