최단 경로 알고리즘 - 플로이드 워셜 알고리즘

드디어 최단 경로 알고리즘!

DFS/BFS의 벽이 너무 높았지만 내가 해냄

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단경로를 구할때 사용하는 알고리즘이다.

 

단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행한다.

이 때 점화식을 사용하게 되므로 일종의 다이나믹 프로그래밍이다.

 

노드의 개수가 n개 일때 n번의 단계를 수행하며 단계마다 n^2의 연산을 통해 모든 경로를 고려하게된다.

총 시간복잡도는 n^3이다.

 

시간복잡도가 큰 만큼 풀 수 있는 유형이 정해져있다.

 

풀이 순서

1. 2차원의 리스트를 무한의 값으로 채워 넣는다.

2. 자기자신에서 자기자신으로 가는 경우는 비용을 0으로 처리

3. 각 간선의 정보를 입력받아 초기화 한다.

4. 플로이드 워셜 알고리즘 수행

 

INF = int(1e9) # 무한의 값으로 설정

# n : 노드의 개수 m : 간선의 개수
n, m = map(int, input().split())

# 2차원 graph를 무한값으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]  

# 자기 자신에서 자기자신으로 가는 경로 0으로 초기화
for a in range(1, n + 1):
	for b in range(1, n + 1):
    	if a == b:
        	graph[a][b] = 0

# 노드, 간선정보 입력받기
for _ in range(m):
	a, b, c = map(int, input().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):
        	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] == INF:
        	print('infinity')
        else:
        	print(graph[a][b]

 

 

출처

이것이 취업을 위한 코딩테스트다. - 나동빈 

https://blog.naver.com/ndb796/221234427842