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

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

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

• 모든 최단 경로를 구하는 알고리즘

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다.

• 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다.

🔍 플로이드-워셜 알고리즘의 과정

모든 노드 간의 최단거리를 구해야 하므로 2차원 인접 행렬을 구성합니다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복합니다.

초기 그래프를 인접행렬로 나타내면 다음과 같습니다. INF는 해당 노드에서 특정 노드까지 가는 길이 없다는 뜻입니다.

• ROUND 1 : 1번 노드를 새로운 중간 노드로 설정

이 그래프는 1번부터 5번 노드까지 존재하므로 알고리즘은 총 5라운드의 과정을 거칩니다. 즉, 모든 노드들을 중간 노드로 선정하는 과정을 각 라운드마다 거칩니다. 예를 들어 2라운드는 2번 노드가 중간 노드이며, 3라운드는 3번 노드가 중간 노드가 될 것입니다.

2번에서 4번으로 가는 길은 원래 없었으나, 1번 노드를 중간 노드로 선정할 경우 2-1-4(길이 5+9=14) 로 갈 수 있게 됩니다. (업데이트된 길이는 📍로 표시)

• ROUND 2 : 2번 노드를 새로운 중간 노드로 설정

1번-3번 노드를 잇는 경로, 3번-5번 노드를 잇는 경로가 새로 생기게 됩니다.

이런 과정으로 5번 노드를 중간 노드로 선정하는 라운드까지 모두 거치면 행렬에는 모든 노드 간 최단 거리가 들어가게 됩니다.

🔍소스코드로 구현

플로이드-워셜 알고리즘은 시간 복잡도가 O(n^3)으로, 그래프의 크기가 작아 세제곱 시간 알고리즘을 적용해도 문제가 풀릴 때만 사용할 수 있습니다.

• 먼저, adj에 저장된 인접 행렬의 값을 활용하여 최단 거리 배열인 dist 배열을 초기화합니다.

1
2
3
4
5
6
7

for(int i = 1; i<=n; i++){
    for(int j =1; j<=n; j++){
        if (i == j) dist[i][j] = 0;
        else if (adj[i][j]) dist[i][j] = adj[i][j];
        else dist[i][j] = INF;
    }
}

• 이후, 각 라운드별로 중간 노드가 될 노드 번호를 for문 가장 바깥의 k로 삼습니다. 내부 이중 for문에는 i, j를 통해 각 노드별 모든 거리를 살펴보면서 k를 중간 노드로 삼을 때와 아닐 때의 값을 비교해 더 작은 값으로 업데이트합니다.

1
2
3
4
5
6
7

for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

• 플로이드-워셜 알고리즘을 활용한 문제
• 2606번 - 바이러스 : https://www.acmicpc.net/problem/2606
  • 플로이드-워셜 알고리즘으로 단순히 경로를 찾는 문제입니다.
• 11404번 - 플로이드 : https://www.acmicpc.net/problem/11404
  • 플로이드-워셜 알고리즘으로 최단 경로를 찾는 문제입니다.