[Python] 최단 경로 플로이드 워셜 알고리즘

https://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 예스24

 

---

플로이드 워셜 알고리즘

모든 지점에서 모든 지점까지의 최단 경로를 구해야 할 때 사용

시간 복잡도: O(N^3)

 

특정 노드를 거쳐서 간 것과 바로 간 것 중 최소를 구한다

점화식: D(ab) = min( D(ab), D(ak)+D(kb) )

 

필요: 최단 경로를 저장하기 위한 2차원 리스트

 

 

최단 경로를 저장하는 graph에 자기 자신은 0으로 초기화

import sys
input = sys.stdin.readline

INF = int(1e9)

n = int(input())

graph = [[INF for _ in range(n+1)] for _ in range(n+1)]

# 자기 자신은 0으로
for i in range(1, n+1):
    graph[i][i] = 0

 

 

노드 연결 정보를 초기화

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

 

 

플로이드 워셜 알고리즘

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

 

출력

for i in range(1, n+1):
    for j in range(1, n+1):
        print(graph[i][j] if graph[i][j] != INF else 'INFINITY', end=' ')
    print()