[알고리즘 개념] 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

플로이드 워셜 알고리즘은 최단경로 알고리즘 중 하나로 다익스트라 알고리즘과 더불어 제일 많이 언급되는 알고리즘 중 하나입니다.

최단 경로 알고리즘을 다시 공부하면서 공부했던 내용을 포스팅 하고자 글을 작성하게 됐습니다.

플로이드 워셜 알고리즘이란?

모든 정점 사이의 최단 경로를 찾는 알고리즘입니다. 최단 경로 알고리즘인만큼 최당경로는 길이 순으로 구해집니다.

플로이드 워셜 알고리즘의 과정입니다.

1. 하나의 정점에서 다른 정점을 바로 갈 수 있으면 최소비용을 설정하며, 갈 수 없다면 INF로 무한대 값을 배열에 값으로 저장합니다.

2. 3중 for 문을 통해 거쳐가는 정점을 설정 한 후 해당 정점을 거쳐가서 비용이 줄어든느 경우에는 값을 바꿔줍니다.

3. 위 과정을 계속해서 반복하여 모든 정점 사이의 최단 경로를 탐색하며 끝냅니다.

 

플로이드 워셜 알고리즘 예시

https://www.acmicpc.net/problem/11404

해당 예시 문제 풀이

import sys
inf = 10000000
n = int(input())
m = int(input())

cost = [[inf]*n for i in range(n)]

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

#경유지
for i in range(n):
    cost[i][i] = 0
    #출발지
    for j in range(n):
        #도착지
        for k in range(n):
            cost[j][k] = min(cost[j][k], cost[j][i]+cost[i][k])

for i in cost:
    for j in range(n):
        if i[j] == inf:
            i[j] = 0
        print(i[j], end= " ")
    print()