최단경로 : 플로이드 워셜 - 이론정리 (미완)

플로이드워셜

• 사용 : 모든 지점에서 다른 모든지점까지의 최단경로 모두 구하는 경우
• 전제조건 :
• 시간복잡도 : O($N^3$)
• 구현개념 :

다익스트라와의 차이점

|

구현 아이디어

$D_{ab}=min(D_{ab}, D_{ak}+D_{kb})$
= min(A에서 B로가는 최소비용, A에서 K를 거쳐 B로가는 최소비용)

동작 과정

[step_0] 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다.

[step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

[step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

[step ~] 3번, 4번, ... 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

시간복잡도 상세

구현 코드

INF = int(1e9)

# 노드의 갯수 및 간선의 갯수 입력받기
n = int(input())
m = int(input())

# 2차원 리스트(그래프 표현)을 만들고, 모든 값을 무한으로 초기화
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라고 설정
	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) :
		# 도달할 수 없는 경우, INF 출력
		if graph[a][b] == INF :
			print("INF", end = " ")
		else :
			print(graph[a][b], end=" ")
	print()

레퍼런스

이것이코딩테스트다