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

플로이드-워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 

• for문을 3번 사용하기 때문에 시간복잡도 O(N^3)이다. 
• 플로이드-워셜 알고리즘은 2차원 테이블에 최단 거리 정보를 저장한다. (모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문)

 

그래프가 다음과 같다고 하자.

모든 정점 사이의 최단 경로를 다음 방법을 통해 찾는다. 

 

i번째 꼭짓점과 j번째 꼭짓점 사이의 거리를 2차원 배열로 입력

 

1. n*n 2차원인 행렬 A0를 만든다. 여기서 n은 정점(노드)의 개수이다. n*n 배열에서 행, 열은 i, j로 인덱싱 된다. (i와 j는 그래프의 정점(노드) 이다)

 

2. 각 A[i][j]는 i번째 꼭짓점에서 j번째 정점까지 떨어진 거리로 채워진다. i번째 정점에서 j번째 정점까지 경로가 없으면 해당 원소를 무한대로 입력한다. (여기서 다른 정점을 통해 연결되었다 하더라도 탐색 전 이므로 무한대 거리라 가정하자)

 

정점 k를 통해 출발정점에서 도착 정점까지 거리를 계산

3. 행렬 A0를 이용하여 새로운 행렬 A1을 만든다. 첫번째 열과 행의 원소들은 그대로 유지하고 나머지 셀을 다음과 같이 채운다. 

 

4. 채우는 방법은 다음과 같다. 정점 k를 출발지에서 목적지까지의 최단 경로에 있는 중간 정점이라고 하자. 이 단계에서 k는 1번 정점이다. 

 

5. A[i][j]는 (A[i][j] > A[i][k] + A[k]) 인 경우 A[i][j] + A[k][j]로 채워진다. 즉 출발지에서 목적지까지의 거리가 정점 k를 통과하는 경로보다 크면 해당 원소는 A[i][j] + A[k][j] 로 채워진다는 의미이다. 

 

(플로이드-워셜의 점화식은 다음과 같다. 수식에서 a,b를 본문에서 i,j 라 생각하자)

 

6. 정점 k를 통해 출발 정점에서 도착 정점까지의 거리를 계산한다.

 

예를들면..

A1행렬에서 A1[2][4]의 경우 정점2에서 정점4까지의 거리는 4이고, 정점 2에서 정점 1 + 정점1에서 정점 4 까지의 거리 합이 7 이므로 4 < 7  이기 때문에 A0[2][4]의 원소는 4로 채워야 한다. 

 

정점2를 통해 출발 꼭짓점부터 도착 꼭짓점까지 거리를 계산한다

7. 마찬가지로 A2 행렬도 A1 행렬을 이용하여 생성할 수 있다. 두번째 행과 열의 요소는 그대로 유지한다.

(이 단계에서 k는 정점2 이다 나머지 단계는 3~6 과정과 동일하다.)

 

정점3을 통해 출발 꼭짓점부터 도착 꼭짓점까지 거리를 계산한다

8. A[3] 행렬도 위와 마찬가지로 구한다.

 

정점4를 통해 출발 꼭짓점부터 도착 꼭짓점까지 거리를 계산한다

9. A[4] 행렬도 위와 마찬가지로 구한다. 

 

플로이드 알고리즘의 pseudo code는 다음과 같다.

 

플로이드 알고리즘을 python 코드로 나타내면 다음과 같다.

# Floyd Warshall Algorithm in python

# The number of vertices
nV = 4
INF = 999

# Algorithm implementation
def floyd_warshall(G):
    distance = list(map(lambda i: list(map(lambda j: j, i)), G))

    # Adding vertices individually
    for k in range(nV):
        for i in range(nV):
            for j in range(nV):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
    print_solution(distance)


# Printing the solution
def print_solution(distance):
    for i in range(nV):
        for j in range(nV):
            if(distance[i][j] == INF):
                print("INF", end=" ")
            else:
                print(distance[i][j], end="  ")
        print(" ")


G = [[0, 3, INF, 5],
     [2, 0, INF, 4],
     [INF, 1, 0, INF],
     [INF, INF, 2, 0]]
floyd_warshall(G)

 

참고

https://www.programiz.com/dsa/floyd-warshall-algorithm

https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm