[이코테] CH09 최단경로 플로이드 워셜 알고리즘 기본 코드

사용되는 경우:

모든 지점에서 다른 모든 지점까지의 최단 경로

 

다익스트라 알고리즘과의 차이점:

다익스트라 : 시작점이 정해져 있다 . 그리디 알고리즘 사용 / 시간복잡도 O(ElogV)

플로이드 워셜 알고리즘: 시작점 정해지지 않음. 다이나믹 프로그래밍과 유사 / 시간복잡도 O(N^3)

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 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):
            if graph[a][b] == INF:
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) # a->b vs a->k->b중 최단경로를 갱신해준다

for a in range(1,n+1):
    for b in range(1,n+1):
        if graph[a][b] == INF:
            print("INFINITY")
        else:
            print(graph[a][b],end=' ')
    print()