플로이드 워셜(Floyd-Warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
그 중에서도 모든 노드 쌍에 대하여 최단거리를 구하는 알고리즘이다.
즉, 그래프에 N개의 노드가 존재한다면 각각의 노드들에 대해서 다른 모든 노드들로 가는 최단거리를 구할 수 있다. 또한 기본적으로 DP(다이나믹 프로그래밍) 기반으로 구현된다.
플로이드 워셜 알고리즘의 가장 큰 특징은 거쳐가는 노드를 기준으로 최단거리를 찾아간다는 점이다.
예를 들어, 아래 그래프가 주어졌다고 하자.
주어진 그래프 정보들을 토대로 초기 상태의 최단 거리 표를 만들어보면 아래와 같다.
인접해 있지 않은 노드 쌍들은 초기 상태에서 최단 거리가 얼마나 되는지 아직 모르기 때문에 무한대로 설정한다.
플로이드 워셜 알고리즘은 이 상태에서 거쳐가는 노드를 기준으로 표를 갱신해 나간다.
예를 들면, 1번 노드를 거쳐가는 노드로 생각해보자.
모든 노드 쌍(i, j) 에 대한 경로( i -> j )에 대해서
- 현재 ( i -> j ) 로 가는 경로의 길이
- ( i -> 1 ) 경로의 길이 + ( 1 -> j ) 경로의 길이
중 최소값으로 표[ i ][ j ]를 업데이트하는 방식이며, 위의 1~2번 과정을 모든 거쳐가는 노드( 1 ~ N )에 대해서 수행하면 알고리즘은 종료된다.
코드로 쓰면 아래와 같다.
int distance[N+1][N+1]; // 최단거리 배열
int edge[N+1][N+1]; // edge 정보
for(int mid=1; mid<=N; mid++)
for(int start=1; start<=N; start++)
for(int end=1; end<=N; end++)
if(distance[start][mid] + distance[mid][end] < distance[start][end])
distance[start][end] = distance[start][mid] + distance[mid][end];PS Tip
플로이드 워셜은 최단거리 알고리즘이지만, 가끔 PS를 하다보면 모든 노드들의 연결 정보를 찾을 때 사용하곤 한다.
예를 들어, 하나의 그래프 안에서 모든 노드들에 대해 인접한 노드들 뿐만 아니라 방문 가능한 모든 노드들을 구해야 하는 상황이다.
즉, 1 -> 2, 2 -> 3 간선이 있는 경우에 1 -> 3 이 연결되어 있다는 정보를 모든 노드들에 대해서 알고 싶은 경우이다. 물론 BFS나 DFS와 같은 알고리즘을 이용해 찾을 수 있지만, 모든 노드들 각각에 대해 한번씩 탐색 알고리즘을 수행하게 되면 코드가 많이 복잡해 질 수 있다.
이럴 경우에 플로이드 워셜 알고리즘을 사용하면 for문 세개의 간단한 구조로 구할 수 있다.
코드로 쓰면 아래와 같다.
int graph[N+1][N+1]; // 인접 행렬 -> 연결되어 있는 경우 1, 아닌 경우 0
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
graph[i][j] |= (graph[i][k] && graph[k][j]);
// i -> k, k -> j 로 가는 간선이 모두 있다면
// i -> j 로 가는 간선이 있다고 인접행렬을 갱신한다. 