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

* 플로이드 워셜 알고리즘이란?

 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. 이번에 알아볼 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.

 

 플로이드 워셜 알고리즘은 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점에서 다익스트라 알고리즘과 다르다. 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 플로이드 워셜의 총 시간 복잡도는 O(N^3)이다.

 

 각 단계에서는 해당 노드를 거쳐 가는 경우를 고려한다. 예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려한다. A -> 1번 노드 -> B로 가는 비용을 확인한 후에 최단 거리를 갱신한다. 플로드 워셜 알고리즘의 점화식은 다음과 같다.

 

 점화식의 의미는 'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신하겠다는 것이다. 

 

* 플로이드 워셜 알고리즘을 사용한 예시

 위의 그래프에서 초기 테이블을 설정하자. 초기 상태 테이블에는 연결된 간선에는 해당 거리 값을 채워 넣고, 연결되지 않은 간선은 '무한'의 값을 넣는다. 2차원 리스트에서 각 값에 해당하는 값은 a에서 b로 가는 최단 거리를 의미한다.

 

 다음 단계에서는 0번 노드를 거쳐 가는 경우를 고려한다. 예를 들어서 3번에서 4번으로 가는 경우는 4가 걸리지만 3 -> 0 -> 4의 경우는 2 + 1로 3이 걸린다. 그렇기 때문에 위 테이블의 [3][4]와 [4][3]은 4에서 3으로 변경된다. 이와 같이 모든 경우를 바꿔주면 된다. 주황색으로 칠해진 부분이 변경된 부분이다.

 

 위와 같이 다음 단계는 1번 노드를 거쳐 가는 경우, 그 다음 단계는 2번 노드를 거쳐 가는 경우를 고려하면 된다. 최종적으로 노드(예제에서는 4번 노드)까지 단계를 거치고 나면 테이블에는 a번 노드에서 b번 노드로 가는 최단 거리가 담기게 된다.

 

* 파이썬으로 구현한 플로이드 워셜 알고리즘

 

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] == INF:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()
 

 

 

* 참고

https://sskl660.tistory.com/61