Floyd-Warshall 알고리즘 구현(python)

Floyd-Warshall 알고리즘

 -최단 경로를 찾는 알고리즘

 -매 단계마다 거쳐가는 노드 k를 기준으로 최단경로를 계산한다

 -즉, a->b로 가는 최단거리와 k를 거쳐 가는 a->k->b의 최단거리를 비교하여 테이블을 갱신한다.

 -2차원 테이블에 최단 거리 정보를 저장한다 (dp임)

---

구현 방법

 1) 최단거리 테이블을 초기화한다. (각 노드에서 인접한 다음 노드로 가는 데 드는 비용을 기록)

 2) 각 노드를 거쳐 가는 경우를 고려하며 테이블을 갱신한다.

---

파이썬 코드

import sys
input = sys.stdin.readline
INF = int(1e9) #매우 큰 숫자인 10억을 무한대로 정의한다

#n(노드 수), m(간선 수) 입력받기
n,m = map(int,input().split())

#최단거리 정보를 저장할 리스트 (초기값은 전부 무한대로 초기화)
graph = [[INF]*(n+1) for _ in range(n+1)]

#자기자신 -> 자기자신으로 가는 비용은 0이므로 0으로 초기화해준다
for i in range(1,n+1):
	for j in range(1,n+1):
    	if i==j:
        	graph[i][j]=0
            
 #간선 정보 입력받기 (a에서 b 노드로 가는 비용이 c)
for _ in range(m):
	a,b,c = map(int, input().split())
   	graph[a][b]=c
    
#Floyd-Warshall 알고리즘 수행
for k in range(1,n+1):	#모든 노드가 k를 거쳐갈때 최단경로를 계산
	for i in range(1,n+1):
    	for j in rnage(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("도달할 수 없음",end=' ')
        else:
        	print(graph[a][b],end=' ')
        print()