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

2023년 10월 27일

플로이드-워셜(Floyd-Warshall)

 

플로이드-워셜 알고리즘이란, 모든 최단 경로를 구하는 알고리즘이다.

 

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라면,

플로이드-워셜 알고리즘은 한 번의 실행으로 모든 정점 간의 최단 거리를 구할 수 있다는 차이로 구분할 수 있다.

 

또한 음수 가중치가 존재하는 가중치 그래프에서는 적용할 수 없는 다익스트라 알고리즘과는 다르게,

플로이드-워셜 알고리즘은 음수 가중치가 존재하는 가중치 그래프에서도 활용할 수 있다.

 

 

---

접근 방법

 

사전 준비

 

플로이드-워셜 알고리즘을 적용하기 위해선, 가중치 그래프가 존재해야 한다.

임의의 가중치 그래프를 예시로 들어보겠다.

 

 

정점은 1~5번까지 총 5개의 정점이 존재하고, 각 정점을 잇는 임의의 간선들은 모두 가중치가 존재한다.

여기서 우리는 모든 간선들 각각을 기준으로 다른 모든 정점들과의 최단 거리를 도출하고자 한다.

 

플로이드-워셜 알고리즘을 적용하기 전, 각 정점 간의 최소경로를 지정해 줄 5 * 5 사이즈의 2차원 테이블을 선언한다.

그리고 각 정점 간의 거리를 아직 모르는 초기 상태이니, 특정 노드에서 다른 노드로의 경로가 존재하지 않다는(정확히는 아직 모른다는) 의미로 INF 값을 기입하여 준다.

	1	2	3	4	5
1	INF	INF	INF	INF	INF
2	INF	INF	INF	INF	INF
3	INF	INF	INF	INF	INF
4	INF	INF	INF	INF	INF
5	INF	INF	INF	INF	INF

 

해당 테이블은 특정 정점 A에서, 임의의 다른 정점 B까지의 거리 데이터를 담을 것이다.

만약 1행 2열 (1, 2) 의 값이 10이라면, 이는 1번 정점에서 2번 정점까지의 최단 거리가 10이라는 뜻이다.

 

그렇다면 위의 가중치 그래프를 바탕으로, 초기값을 완벽하게 세팅해보도록 하겠다.

 

	1	2	3	4	5
1	0	2	INF	6	INF
2	2	0	1	3	INF
3	INF	1	0	1	INF
4	6	3	1	0	2
5	INF	INF	INF	2	0

 

대각선 요소는 행과 열 값이 같은, 다시 말해 자신의 정점으로부터 자신의 정점까지의 최단 거리를 담아내는 위치이므로, 0을 대입하여 준다.

 

양방향 그래프이다보니 대각선을 기준으로 대칭인 모습을 보인다.

만약 단방향 그래프라면 대칭이 아닐 것이라고 추측이 가능하다.

 

플로이드 워셜을 적용하기 전 필요한 2 가지인 가중치 그래프와 각 정점 간의 거리 데이터를 담아낼 2차원 테이블을 세팅해주었다.

 

알고리즘 적용

 

알고리즘 적용 개념은 다음과 같다.

 

특정 정점 A에서 B가 있을 때,

1. 두 정점 사이의 거리는 중간점을 거치치 않고 바로 가는 A->B 경로가 존재할 것이다.
2. 또한 중간에 임의의 중간점인 C 정점을 거치는 A->C->B 경로도 존재할 것이다.
3. 또한 중간에 다른 임의의 중간점인 D 정점을 거치는 A->D->B 경로도 존재할 것이다.
4. A->B의 최단 거리는 이 모든 경우의 수 중의 최소값이다.

위의 흐름대로, 모든 경우의 수를 다 체크해보며 모든 정점들 간의 최단 거리를 알아낼 것이다.

 

우리는 임의의 중간점을 계속 변경해주며, 각 정점 간의 최소 거리를 계속 갱신시켜줄 것이다.

 

Case 1 : 1번 정점을 중간점으로 지정

 

1번 정점을 무조건 거쳐가야하는 중간점으로 지정하고, 각 정점 간의 최소거리를 갱신시켜줄 수 있는지 확인해보자.

 

초기 가중치 그래프를 보며 확인해보자

 

아쉽게도, 갱신시켜줄만한 요소가 없다. 예를 들어 1번 정점을 거쳐 다른 정점으로 갈 수 있는 2 -> 1 -> 4 경로의 경우, 기존 2 -> 4 거리는 3인데 반해 2 -> 1 -> 4 경로는 2 + 6 = 8로, 거리가 더 늘어나게 됨을 알 수 있다.

 

	1	2	3	4	5
1	0	2	INF	6	INF
2	2	0	1	3	INF
3	INF	1	0	1	INF
4	6	3	1	0	2
5	INF	INF	INF	2	0

(Case 1 완료 후, 테이블 상태)

 

 

Case 2 : 2번 정점을 중간점으로 지정

 

2번 정점을 무조건 거쳐가야하는 중간점으로 지정하고, 각 정점 간의 최소거리를 갱신시켜줄 수 있는지 확인해보자.

 

초기 가중치 그래프를 보며 확인해보자

 

2번 정점을 거쳐가게 되니, 기존에는 경로가 존재하지 않았던 1 -> 3 경로가, 1 -> 2 -> 3 경로로 가능하게 되었다.

테이블의 [1, 3], [3, 1] 요소에 해당 경로의 거리인 2 + 1 = 3 값으로 치환한다.

 

또한, 1 -> 4 의 거리가 6이었으나 2번 정점을 거치는 1 -> 2 -> 4 경로의 거리가 2 + 3 = 5로 더 짧다는 것을 알아냈다.

테이블의 [1, 4], [4, 1] 요소에 해당 경로의 거리인 5로 치환한다.

	1	2	3	4	5
1	0	2	3	5	INF
2	2	0	1	3	INF
3	3	1	0	1	INF
4	5	3	1	0	2
5	INF	INF	INF	2	0

(Case 2 완료 후, 테이블 상태. 갱신된 데이터는 빨간색으로 표시)

 

 

Case 3 : 3번 정점을 중간점으로 지정

 

3번 정점을 무조건 거쳐가야하는 중간점으로 지정하고, 각 정점 간의 최소거리를 갱신시켜줄 수 있는지 확인해보자.

 

초기 가중치 그래프를 보며 확인해보자

 

3번 정점을 중간점으로 지정하니, 2 -> 4 경로의 거리인 3이, 2 -> 3 -> 1 경로인 1 + 1 = 2 거리로 더 짧은 거리의 경로가 존재함을 알아냈다.

테이블의 [2, 4], [4, 2] 요소에 해당 경로의 거리인 2 값으로 치환한다.

 

또한, 1 -> 4의 최소 거리는 현재 5 이지만, 3을 거쳐가는 1 -> 3 -> 4 경로는 3 + 1 = 4 이므로, 최소 거리를 갱신시켜준다.

테이블의 [1, 4], [4, 1] 요소에 해당 경로의 거리인 4 값으로 치환한다.

	1	2	3	4	5
1	0	2	3	4	INF
2	2	0	1	2	INF
3	3	1	0	1	INF
4	4	2	1	0	2
5	INF	INF	INF	2	0

(Case 3 완료 후, 테이블 상태. 갱신된 데이터는 빨간색으로 표시)

 

 

 

Case 4 : 4번 정점을 중간점으로 지정

 

4번 정점을 무조건 거쳐가야하는 중간점으로 지정하고, 각 정점 간의 최소거리를 갱신시켜줄 수 있는지 확인해보자.

 

초기 가중치 그래프를 보며 확인해보자

 

4번을 중간점으로 지정하니, 기존에 존재하지 않았던 경로들이 다수 발견되었다.

 

1 -> 5 경로가, 1 -> 4 -> 5 경로로 가능하게 됨. 거리 : 4 + 2 = 6

2 -> 5 경로가, 2 -> 4 -> 5 경로로 가능하게 됨. 거리 : 2 + 2 = 4

3 -> 5 경로가, 3 -> 4 -> 5 경로로 가능하게 됨. 거리 : 2 + 1 = 3

 

해당 값들을 테이블의 적절한 위치에 삽입시켜 정점 간의 최소거리를 갱신시켜준다.

 

 

	1	2	3	4	5
1	0	2	3	4	6
2	2	0	1	2	4
3	3	1	0	1	3
4	4	2	1	0	2
5	6	4	3	2	0

(Case 4 완료 후, 테이블 상태. 갱신된 데이터는 빨간색으로 표시)

 

 

 

 

Case 5 : 5번 정점을 중간점으로 지정

 

5번 정점을 무조건 거쳐가야하는 중간점으로 지정하고, 각 정점 간의 최소거리를 갱신시켜줄 수 있는지 확인해보자.

 

초기 가중치 그래프를 보며 확인해보자

 

5번 정점을 중간점으로 지정했을 때의 경우의 수가 존재하지 않으므로, 이번 케이스의 연산은 생략해준다.

 

정확히 말하면, 5번 정점을 중간점으로 두었을 때, 무조건 기존 거리보다 멀어질 수 밖에 없는 구조이기 때문이다.

4 -> 2 경로로 예시를 들자면,
5를 중간점으로 두는 4 -> 5 -> 2는 4 정점에서 5 정점으로 갔다가, 다시 5 정점에서 2 정점으로 가는 마치 한 간선을 2번 이상 왕복하는 구조를 띄게되므로 최소거리가 무조건 성립될 수 없는 구조이다.

 

 

수행 결과

 

플로이드-워셜 알고리즘 수행 결과로 산출된 테이블은 다음과 같다.

 

	1	2	3	4	5
1	0	2	3	4	6
2	2	0	1	2	4
3	3	1	0	1	3
4	4	2	1	0	2
5	6	4	3	2	0

(최종 테이블 상태)

 

 

 

---

 

코드

 

핵심 알고리즘 구현 코드는 다음과 같다.

 

k = 현재 지정한 중간점, i = 행, j = 열이라고 가정했을 때,
그리고 정점의 개수가 n이라고 가정했을 때,

for k in range(1, n+1):
     for i in range(1, n+1):
          for j in range(1, n+1):
               table[ i ][ j ] = min( table[ i ][ j ] , table[ i ][ k ] + table[ k ][ j ]) 

 

중간점 k를 무조건 거쳐간다고 가정해보았을 때, 두 정점 i와 j 간의 최소거리가 기존의 거리보다 더 짧으면 갱신시켜주는 부분이다.

 

---

시간 복잡도

플로이드-워셜 알고리즘의 시간 복잡도는 위 코드 템플릿 부분에서 볼 수 있듯이, O(n ^ 3)이다.

다시 말해, 그래프의 크기가 작아 세제곱의 시간 알고리즘을 적용해도 문제가 풀릴 때에만 사용할 수 있다는 점을 알 수 있다.

 

---

응용 문제

실제 플로이드-워셜 알고리즘을 활용한 문제를 풀어보자. 백준 11404번 - 플로이드 문제를 추천한다.

---

문제 풀이

문제 링크 : 백준 11404번 - 플로이드

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

 

알고리즘 분류

• 그래프 이론
• 플로이드-워셜
• 최단 경로

---

문제 접근

기초적인 플로이드-워셜 알고리즘 응용 문제이다.

---

입력 예제

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

 

출력 예제

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

---

주의할 점

처음에 했던 실수인데, 초기 2차원 테이블 세팅할 때 대입한 값을 100,001로 했다가 틀렸습니다! 당했다.

각 정점 간의 간선의 최대 가중치가 100,000임을 보고 세팅한 것인데, 이렇게하면 다음과 같은 애로사항이 발생한다.

 

A 정점에서 B 정점으로의 기존 거리가 존재하지 않는 INF로 세팅되어 있다고 가정.
A -> C 거리는 100,000이고 C -> B 거리는 100,000이라고 가정하겠다.

A  -> B 정점은 C 정점을 거치는 A -> C -> B 경로로 가능하고, 해당 경로는 200,000이다.
그러나 플로이드-워셜 핵심 코드 중, A -> B 거리와 A -> C -> B 거리의 최소값을 채택하는 과정에서 INF가 100,001이므로 200,000보다 작다고 판단, 기존 값인 INF 값을 채택해버리는 오류를 범하게 된다.

 

INF는 가능한 어떤 경우의 수가 나오더라도 그 이상으로 존재할 수 없는 최대값이어야 한다.

이는 노드가 100개 존재하고, 각 노드가 일직선으로 연결되어 있고, 각 정점간의 간선이 모두 100,000이라고 가정했을 때,처음 정점과 마지막 정점 사이의 거리인 100,000 * 100보다 커야한다.

 

INF는 최소 100,000 * 100 + 1 이어야 한다.

---

전체 코드

# 11404


def Floyd_Warshall():
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                city[i][j] = min(city[i][j], city[i][k] + city[k][j])
    
    for row in range(1, n+1):
        for col in range(1, n+1):
            if city[row][col] == INF:
                print(0,end = ' ')
            else:
                print(city[row][col],end = ' ')
        print()

if __name__ == "__main__":

    INF = 100000 * 100 + 1

    n = int(input())
    
    # 각 도시까지의 최단경로 데이터를 저장할 n+1 * n+1 사이즈의 2차원배열 생성
    # 0행 0열은 더미 값.
    # 특정 두 도시끼리 버스 경로에 대해 플로이드-워셜 알고리즘을 이용해 최소값을 게속 갱신해야 하므로 각 요소는 최대값으로 초기화
    city = [[INF for _ in range(n + 1)] for _ in range(n + 1)]

    # city의 대각선 요소는 같은 도시끼리의 경로에 대한 최소시간이므로 0으로 초기화
    for dia in range(n+1):
        city[dia][dia] = 0
    
    m = int(input())

    for _ in range(m):
        a, b, time = map(int,input().split())
        # a 도시에서 b 도시로 가는 버스가 존재하며, 시간은 time만큼 걸림.
        # city[a][b]는 a에서 b로 가는 최소시간을 저장할 것이며, 초기 소요 시간인 time을 저장한다.
        # a 도시에서 b로 가는 버스의 소요 시간이 2개 이상일 경우, 최소값만을 유효하게하기 위해 min 함수 사용.
        city[a][b] = min(time, city[a][b])
    
    
    Floyd_Warshall()

---

풀이 후기

플로이드-워셜 알고리즘의 기본 개념과 적용 방법을 알고있다면 쉽게 풀 수 있는 문제였다.

이런 문제는 더욱이 조심해야 하는 부분이, 초기 테이블 세팅에 필요한 초기값이라고 생각한다.