[이코테] 9장 최단 경로 - 플로이드 워셜 알고리즘

다익스트라 알고리즘 : 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우
플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

다익스트라와 차이점

1. 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다.
2. 모든 노드에 대해 다른 모든 노드로 가는 최단 거리 정보를 담기 위해 2차원 리스트를 사용한다.
3. 다이나믹 프로그래밍을 사용한다.
4. $_{(n-1)}P_2$ 가지 경우에 대해서만 고려하면 된다.
5. 시간 복잡도 : $O(N^3)$

점화식

A -> B로 가는 최소 비용과 A -> K -> B로 가는 비용을 비교해 더 작은 값으로 갱신

$D_{ab} = min(D_{ab}, \space D_{ak} + D_{kb})$

알고리즘 코드

INF = int(1e9)  

# n : 노드 수, m : 간선의 수
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 = 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("INF", end=' ')
        # 도달 가능한 경우
        else:
        	print(graph[a][b], end=' ')
        
        print()