<aside> 🔥 플로이드 워셜이란?

모든 지점에서 다른 모든 지점까지의 최단거리를 구해주는 알고리즘.

1. 2차원 거리 목록 테이블을 생성한다.

2. 2차원 거리 목록을 모두 무한대로 설정.

3. 자기 자신으로 가는 비용을 0으로 설정.

4. 간선으로 연결되어 있는 노드 거리 테이블에 업데이트.

5. 점화식을 이용하여 경로를 거쳐 가는것과 직접 가는것의 최소값으로 테이블 업데이트

   점화식 : $D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

</aside>

<aside> 🔥 기본 구현 코드

4  # 노드의 개수
7  # 간선의 개수

# 시작점, 도착점, 시작 -> 도착 비용
1 2 4  
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

import sys
from collections import defaultdict
from pprint import pprint

from min_cost.floyd_warshall import floyd_warshall

with open('testcase_fw.txt') as f:
    sys.stdin = f
    input = sys.stdin.readline

    N = int(input())
    M = int(input())

    graph = defaultdict(list)
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))

    pprint(floyd_warshall(graph))

INF = int(1e9)

def floyd_warshall(graph):
    N = len(graph)
    dist = [[INF] * (N + 1) for _ in range(N + 1)]

    for idx in range(1, N + 1):
        dist[idx][idx] = 0

    for start, adjs in graph.items():
        for adj, d in adjs:
            dist[start][adj] = d

    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    return dist

</aside>