[파이썬 알고리즘] 플로이드 워셜(Floyd-Warshall) 알고리즘

[파이썬 알고리즘] 플로이드 워셜(Floyd-Warshall) 알고리즘

 

플로이드 워셜 알고리즘이란?

모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘으로 다익스트라 알고리즘을 정점수만큼 반복하는 거와 같은 결과값을 가지지만

시간복잡도가 O(n³) 이기에 정점의 수가 적을때에는 다이스트라 알고리즘보다 빠른 결과값을 받을 수 있다.

 

알고리즘 동작 과정

1. 비용 테이블 초기화:
   • 모든 정점 간의 최단 거리 정보를 담는 테이블을 생성합니다. 처음에는 무한대(inf)로 설정하여, 아직 연결되지 않은 상태를 나타냅니다.
2. 간선 정보 입력:
   • 간선 정보를 입력받아, 두 정점 사이의 거리를 그래프 테이블에 입력합니다. 간선 정보는 (a, b, c) 형식으로, a에서 b로 가는 거리가 c라는 뜻입니다.
3. 자기 자신으로 가는 거리는 0으로 설정:
   • 모든 정점에서 자기 자신으로 가는 거리는 0으로 설정합니다.
4. 3중 for문을 사용하여 최단 경로 계산:
   • 첫 번째 for문에서 거쳐가는 중간 정점 k를 선택합니다.
   • 두 번째 for문에서 출발 정점 i를 선택하고,
   • 세 번째 for문에서 도착 정점 j를 선택합니다.
   • 그 후, i에서 j로 가는 기존의 최단 경로와, i에서 k를 거쳐 j로 가는 경로를 비교하여 더 짧은 경로를 비용 테이블에 저장합니다.

 

코드

Inf=9999999999
n=int(input()) #정점수
v=int(input()) #간선수

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


#간선정보 그래프에 넣기
for _ in range(v):
	a,b,c=map(int,input().split())
	graph[a][b]=c

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

#거쳐가야할 지점
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])