알고리즘 - 플로이드 워셜

가중치가 있는 그래프에서 모든 노드에서 모든 노드로 이동할때의 최소비용은 어떻게 구할까?

다익스트라 알고리즘으로 가중치가있는 그래프에서 출발지로부터 다른 목적지까지 최소비용으로 탐색하는 법을 알 수 있었다.

그러나 출발지가 한 곳이 아니라 모든노드에서 출발하여 모든 노드로 도착할때 최소비용은 어떻게 구할까?

플로이드 워셜 알고리즘은
다이나믹 프로그래밍 알고리즘을 이용한다.
2차원 배열에 최소비용이 발견될때마다 값을 갱신한다.
다른 노드를 거쳐가는 경우를 확인한다.

import sys
import math

input = sys.stdin.readline

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

graph = [[math.inf]*(N+1) for _ in range(N+1)]

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

for _ in range(M):
    a,b,c = map(int, input().split())
    graph[a][b] = min(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 a in range(1, N+1):
    for b in range(1, N+1):
        if graph[a][b] == math.inf:
            print(0, end = ' ')
        else:
            print(graph[a][b], end=' ')
    print()

플로이드 워셜 알고리즘의 시간복잡도는 O($N^3$)이다.
노드의 갯수가 500정도만 되도, 1억2천5백만번을 연산 해야하므로
시간초과의 위험이 있다.

따라서 노드의 갯수가 적을때 사용해볼 수 있을 것이다.