이코테 플로이드 워셜 알고리즘

import sys
import heapq
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 8)
sys.stdin.readline 
import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(10 ** 8)
sys.stdin.readline 
INF = int(1e9)

N = int(input())
M = int(input())
graph = [[INF] * (N+1) for _ in range(N+1)]

for i in range(1,N+1):
    for j in range(1,N+1):
        if i == j:
            graph[i][j] = 0

for _ in range(M):
    a,b,c = map(int,sys.stdin.readline().split())
    graph[a][b] = c

for k in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])
        
for i in range(1,N+1):
    for j in range(1,N+1):
        if graph[i][j] == INF:
            print("INFINITY")
        else:
            print(graph[i][j],end = " ")
    print()

다이나믹 프로그래밍과 매우 유사하다. a->b 와 a->k->b를 비교하여 최솟값 찾기

O(N^3)의 시간이 소요된다

모든 시작점에서 모든 최단루트를 찾는 경우에 사용