[알고리즘] 플로이드 워셜

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

플로이드 워셜 알고리즘은 플로이드와 워셜이 개발한 알고리즘으로 그래프의 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.

데이크스트라 알고리즘과 비슷하게 단계별로 거쳐 가는 노드를 기준으로 최소값을 갱신하지만, 데이크스트라 알고리즘은 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾아서 방문하였다면 이 플로이드 워셜 알고리즘은 아묻따 모든 노드를 탐색한다.

인접 행렬 형태의 2차원 테이블을 만들어 최단 거리 정보를 저장한다. 이전에 한번 한 연산은 다시 반복하지 않는다는 점에서 다이나믹 프로그래밍 유형에 속한다.

 

이 알고리즘은 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인하여 갱신해준다.

a에서 b로 가는 최단 경로와 a에서 k를 거쳐 b로 가는 최단 거리를 비교하여 검사한다.

즉 점화식을 세우면 다음과 같다.

 

구현은 삼중 반복문을 돌려 테이블을 갱신한다.

 

어떻게 동작하는지 살펴보자

그래프

위와 같은 그래프가 있다.

초기 상태의 최단 거리 테이블은 인접한 노드에서만 이동하여 다음과 같이 초기화 시켜준다.

출발\도착	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	INF
3번	5	INF	0	4
4번	INF	INF	2	0

 

1번 노드에서 1번 노드로 가는 것인 비용이 들지 않고, 현재로서 갈수 없다면 무한으로 초기화 시켜주었다.

 

스텝1

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

 

 

2번 노드에서 4번 노드가 서로 이웃하지 않아 초기 테이블에는 무한 값이었지만 1번 노드를 방문하면 갈 수 있어 2번에서 4번 가는 최단경로는 2번 노드 -> 1번 노드(3) + 1번 노드 -> 4번 노드(6) 값인 9로 갱신된다.

 

이와 같이 2번 노드를 거쳐 가는 경우, 3번 노드를 거쳐 가는 경우, 4번 노도를 거쳐 가는 경우를 고려하여 테이블을 갱신해주면 모든 노드에서 다른 모든 노드까지의 최단 거리를 파악할 수 있다.

 

1번 부터 4번까지 반복적으로 갱신해주면 다음과 같이 최단 거리 테이블은 갱신된다.

 

출발\도착	1번	2번	3번	4번
1번	0	4	8	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

 

소스코드는 다음과 같다.

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
 
# 노드의 개수 및 간선의 개수를 입력받기
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):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == int(1e9):
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()

출처: https://github.com/ndb796/python-for-coding-test/blob/master/9/3.py

 

플로이드 워셜 알고리즘의 시간 복잡도는 3중 반복문을 돌기에 O(N^3)이다. 때문에 노드의 갯수가 1000을 넘어간다면 10억 번 정도의 연산을 하게 되므로 시간 초과가 발생할 수 있다.