[TIL] 플로이드-워셜 - Floyd-Warshall

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

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘
• 2차원 테이블에 최단 거리 정보를 저장한다.
• 다이나믹 프로그래밍 유형에 속한다.
• 각 단계마다 특정 노드 k를 거쳐 가는 경우를 확인하여 a-b의 최단 거리보다 a-k-b가 짧은지 검사한다.

 

 

플로이드-워셜 알고리즘 문제

1956번: 운동 (acmicpc.net)

1956번: 운동

import sys
#플로이드 워셜
input = sys.stdin.readline

v,e = map(int, input().split())
INF = int(1e9)
graph = [[INF] *(v+1) for _ in range(v+1)]

for _ in range(e):
    a,b,c = map(int, input().split())
    graph[a][b] = c
    
for k in range(1, v+1):
    for i in range(1, v+1):
        for j in range(1, v+1):
            graph[i][j] = min(graph[i][j] , graph[i][k]+graph[k][j])
            
            
rst = INF
for i in range(1,v+1):
    rst = min(rst, graph[i][i])
    
if rst ==INF:
    print(-1)
else:
    print(rst)

 

플로이드 워셜 알고리즘은 3중 for문을 돌며 

각 노드에서 특정한 노드 k를 거쳐가는 경우를 확인하며 최단거리를 갱신한다.

3중 for문에서 k는 거쳐가는 노드, i는 시작 노드, j는 끝 노드이다.

 

비교적 간단한 알고리즘인데 3중 for문을 사용하기 때문에

시간복잡도가 O(N**3)이나 된다.

고려할 노드의 수가 적을 때는 상관없지만

그 수가 많아지면 다른 알고리즘을 사용하는 것이 훨씬 효율적일 것이다.