[알고리즘 개념 정리] 플로이드 워셜 (Python)

 

[이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘을 듣고 정리한 내용입니다.

 

플로이드 워셜 알고리즘

- 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다.

- (다익스트라 알고리즘과 마찬가지로) 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만, 다익스트라 알고리즘과 달리 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다.

- 2차원 테이블에 최단거리 정보를 저장한다. 

- 다이나믹 프로그래밍 유형에 속하며, 시간 복잡도는 O(n³)이다.

- 노드의 갯수가 적은 경우에 사용이 적합하며, 노드와 간선의 갯수가 많은 경우에는 다익스트라 알고리즘을 활용해야하는 경우가 많다.

    실제로도 플로이드 워셜 알고리즘을 활용하는 문제는 노드의 개수가 500개가 넘어가지 않는 경우가 많다.

 

풀이 방법

각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인한다.

    a에서 b로 가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.

플로이드 워셜 점화식

 

동작 과정

1. 문제에서 위 그래프와 같이 출발, 도착, 거리가  주어지는 경우 오른쪽 2차원 그래프와 같이 미리 거리를 초기화해놓는다.

 

2. n번 노드를 거쳐가는 경우를 고려해 테이블을 갱신한다.

    a -> b로 가는 거리와 a -> 1, 1 -> b로 가는 거리 중 작은 값으로 갱신하는 과정이다.

    하늘색으로 표시된 부분이 갱신되는 부분이다.

    색칠이 되지 않은 부분을 보면 n번을 거쳐가는 정보를 확인하고 있기 때문에 n번 행과 n번 열에서는 갱신되는 정보가 없다.

    또한 자기 자신에서 자기 자신으로 가는 노드는 갱신되지 않는다.

 

구현 코드

INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

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

# 2차원 리스트를 만들고 무한으로 초기화
grahp = [[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):
    	# 도달할 수 없는 경우 INFINITY 출력
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        else:
            print(graph[a][b], end=" ")