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

플로이드 워셜 알고리즘

 

🔎 플로이드 워셜(Floyd-Warshall) 알고리즘 이란?

• '모든 정점' 에서 다른 '모든 정점' 까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘
• '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것이 핵심 아이디어 

 

📒 플로이드 워셜 알고리즘 구현 과정 

모든 노드 간의 최단 거리를 구해야 하므로 2차원 인접 행렬을 구성한다. 가능한 출발 노드 → 도착 노드의 단계를 모두 수행하며 각 단계마다 거쳐가기 위한 경유 노드를 선택하고, 더 짧은 거리로 갈 수 있는 노드가 나온다면 거리의 값을 줄이는 과정을 반복한다. 

 

다음과 같은 그래프를 2차원 인접 행렬로 나타내면 다음과 같다. 노드간 갈 수 있는 경로가 없다면 무한으로 표시한다. 목적이 노드간 최소 경로값을 구하는 것이기 때문에 무한히 큰 수로 초기화. 

 

0	5	무한	9	1
5	0	2	무한	무한
무한	2	0	7	무한
9	무한	7	0	2
1	무한	무한	2	0

 

• 1 단계 : 1번 노드를 경유 노드로 설정 

이 그래프는 1~5까지 5개의 노드를 가지고 있기 때문에 총 5단계의 과정을 거친다. 즉, 1~5까지 모든 노드들을 경유 노드로 한번씩 선정한다. 

 

1번 노드를 경유 노드로 하여, 기존에 없었던 경로를 업데이트 하거나 더 짧은 경로로 갱신한다. 예를 들어 2번에서 4번으로 가는 경로는 원래 없었기 때문에 무한으로 설정해 두었으나, 1번 노드를 경유하여 갈 경우, 2→1 + 1→4 (5+9=14)로 갈 수 있게 된다. 

 

0	5	무한	9	1
5	0	2	14	6
무한	2	0	7	무한
9	14	7	0	2
1	6	무한	2	0

 

• 2 단계 : 2번 노드를 경유 노드로 설정 

1번에서 3번으로 갈 수 있는 경로는 없었지만, 1→2 + 2→3 (5+2=7)로 갈 수 있다. 

 

0	5	7	9	1
5	0	2	14	6
7	2	0	7	8
9	14	7	0	2
1	6	8	2	0

 

이러한 단계를 5번 노드까지 경유 노드로 설정하여 거치게 되면, 2차원 인접 행렬에는 모든 노드간의 최단 거리가 저장된다. 

 

 

✏️ 점화식

• D_ab = min (D_ab, D_ak + D_kb ) 

 

a → b 노드 간 거리 = (a → b 노드 간 거리) vs (a → k + k → b 의 노드 간 거리의 합) 

즉, a 에서 b로 바로 가는 값과 중간 노드를 경유해 가는 값을 비교하여 최솟값으로 업데이트한다. (모든 노드 기준)

이 과정을 위해 노드 간 경로가 없을 경우 초기값을 무한 으로 설정하였다. 

 

 

💡 정리 

출발노드, 경유노드, 도착노드의 후보가 주어진 n개의 모든 노드이기 때문에 3중 반복문을 이용하여 위의 점화식에 따라 최단 거리 테이블을 갱신하면 된다. 3중 반복문의 순서는 '경-출-도' (경유-출발-도착) 

• 초기 테이블 설정 시, '연결 되지 않은 간선' ( 경로가 없을 경우 ) 무한값을 넣는다. 
• 자기 자신으로 가는 비용은 모두 0으로 초기화한다. 왼쪽 위에서 오른쪽 아래로의 대각선