[알고리즘] 플로이드 와샬(Floyd Warshall) - 모든 정점의 최소 비용

플로이드 와샬(Floyd Warshall)

• 모든 정점에서 모든 정점으로의 최단 경로를 구하기 위해 사용하는 알고리즘
• 무방향, 방향 그래프에서 사용 가능하지만 음수 사이클이 있으면 X

 

플로이드 와샬 구현 방법

• 일단 자기 자신은 0, 간선 1개로 얻을 수 있는 값들로 2차원 배열(최단 거리 테이블)을 만든다.
• x에서 y로 가는 최소 비용 vs x에서 노드1으로 가는 최소 비용 + 노드 1에서 y로 가는 최소 비용
  • ex. D[2, 3] = min((D[2,1] + D[1,3]), D[2,3])
• 1부터 n까지의 노드들 최소 비용 갱신

 

플로이드 와샬 문제 - 11404번 플로이드

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

11404번: 플로이드

#n = 5 # 도시의 개수
#m = 14 # 버스의 개수
n = int(input())
m = int(input())
inf = float('inf')
dp = [[inf for _ in range(n+1)] for _ in range(n+1)] # 최소 비용 테이블
# 버스의 정보 : 시작 도시 a, 도착 도시 b, 필요 비용 c
for _ in range(m):
    a, b, c = map(int, input().split())
    dp[a][b] = min(c, dp[a][b])

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j: # 자기 자신은 X
                dp[i][j] = 0
            else:
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

for x in range(1, n+1):
    for y in range(1, n+1):
        if dp[x][y] == inf:
            print(0, end=' ')
        else:
            print(dp[x][y], end=' ')
    print()