[Algorithm] 최단 경로 탐색(Shortest Path) - 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

개요

 

◎ 플로이드 워셜 알고리즘이란?

◎ 그림 예시

◎ 구현 코드 (Java)

◎ 시간 복잡도

◎ 다익스트라 알고리즘과 비교

 

 

 

안녕하세요. J4J입니다.

 

이번 포스팅은 플로이드 워셜 알고리즘에 대해 적어보는 시간을 가져보려고 합니다.

 

 

플로이드 워셜 알고리즘이란?

 

플로이드 워셜 알고리즘은 정점들 간의 최단 경로를 탐색하기 위한 알고리즘 기법으로 시작 정점과 도착 정점 외에도 중간 정점을 선택하여 최소 거리를 탐색하는 방법을 사용합니다.

 

예를 들어 A, B, C, D, E 정점이 있다고 가정하면 다음과 같이 탐색을 합니다.

 

1-1. 중간 정점을 A로 선택합니다.

1-2. 모든 정점들 간의 거리를 중간 지점인 A를 거쳐서 가는 거리와 비교하여 최솟값들을 저장합니다.

 

2-1. 중간 정점을 B로 선택합니다.

2-2. 모든 정점들 간의 거리를 중간 지점인 B를 거쳐서 가는 거리와 비교하여 최솟값들을 저장합니다.

 

.

.

.

 

 

그림 예시

 

위의 과정을 그림으로 표현하면 다음과 같이 표현됩니다. (A: 0, B: 1, C: 2, D: 3, E: 4)

 

파란색으로 표현된 노드는 중간 지점으로 선택된 노드이며 표의 값들은 중간 노드를 거쳐서 가는 것과 기존의 거리의 최솟값들을 표현한 것입니다.

 

 

 

 

구현 코드 (Java)

 

플로이드 워셜의 구현 코드는 생각보다 간단한 편입니다.

 

단순히 3중 for문을 이용하여 다음과 같이 구현할 수 있습니다.

 

package shortest;

import java.util.Arrays;

public class FloydWarshall {
	public static void main(String[] args) {
		int N = 5; // 정점의 갯수
		int graph[][] = new int[N][N]; // 정점 간 거리 저장
		
		init(graph); // 초기화, graph의 모든 간선의 거리를 정수 최대값으로 초기화 / 자신에게 가는 길은 0으로 초기화
		             // 정수 최대값인 경우는 길이 없다는 것을 의미
		
		// 길(간선) 추가
		add(0, 2, 3, graph);
		add(0, 3, 5, graph);
		add(1, 2, 4, graph);
		add(1, 3, 4, graph);
		add(2, 4, 2, graph);
		add(3, 4, 1, graph);
		
		for(int k=0; k<N; k++) { // 중간 정점 순회
			System.out.println(k + "번째");
			for(int i=0; i<N; i++) {
				System.out.println(Arrays.toString(graph[i]));
			}
			
			for(int i=0; i<N; i++) { // 시작 정점 순회
				if(i == k) { // 인덱스가 같을 경우
					continue;
				}
				
				for(int j=0; j<N; j++) { // 도착 정점 순회
					if(j == k || j == i) { // 인덱스가 같을 경우
						continue;
					}
					
					if(graph[i][k] != Integer.MAX_VALUE && graph[k][j] != Integer.MAX_VALUE) { // 길(간선)이 존재할 경우
						graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
					}
				}
			}
		}
		
		for(int i=0; i<N; i++) {
			System.out.println(Arrays.toString(graph[i]));
		}
		
		// [0, 7, 3, 5, 5]
		// [7, 0, 4, 4, 5]
		// [3, 4, 0, 3, 2]
		// [5, 4, 3, 0, 1]
		// [5, 5, 2, 1, 0]
	}
	
	public static void add(int v, int u, int distance, int graph[][]) { // 가중치 추가
		graph[u][v] = graph[v][u] = distance;
	}
	
	public static void init(int graph[][]) { // 값 초기화
		int N = graph.length;
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				graph[i][j] = Integer.MAX_VALUE;
			}
		}
		
		for(int i=0; i<N; i++) {
			graph[i][i] = 0;
		}
	}
}

 

 

시간 복잡도

 

플로이드 워셜의 시간 복잡도는 O(N^3)입니다.

 

3중 for문만을 이용하여 최단 경로를 구하기 때문에 N x N x N = N^3이라는 시간이 소요됩니다.

 

 

다익스트라 알고리즘과 비교

 

다익스트라 알고리즘과 플로이드 워셜 알고리즘의 가장 큰 차이는 모든 정점에 대해 최단 경로를 구하느냐입니다.

 

다익스트라 알고리즘은 하나의 정점에 대해서만 다른 정점들간의정점들 간의 최단 경로를 구할 수 있지만 플로이드 워셜 알고리즘은 모든 정점에 대해서 다른 정점들 간의 최단 경로를 구할 수 있습니다.

 

물론 다익스트라를 이용해서도 플로이드 워셜처럼 for문 하나를 추가하여 모든 정점에 대한 최단 경로를 구할 수 있습니다.

 

하지만 모든 정점에 대한 최단 경로를 구한다면 구현이 까다로운 다익스트라를 이용하는 것보다 플로이드 워셜을 사용하는 것이 더 효율적일것입니다.

 

시간 복잡도 또한 다익스트라의 시간 복잡도인 O(N^2)에 N만큼 더 순회하므로 플로이드 워셜과 동일하게 O(N^3)이라는 동일한 결과가 나옵니다.

 

그렇기에 모든 정점에 대한 최단 경로를 구한다면 다익스트라보다는 플로이드 워셜을 사용하는 것을 추천드립니다.

 

 

정리

 

● 플로이드 워셜 알고리즘은 최단 경로를 탐색하기 위한 알고리즘 기법

● 중간 정점을 선택하여 정점들간의 최소 거리를 계산함

● 다익스트라와 달리 모든 정점에 대해 다른 정점들 간의 최단 경로를 구함

● 시간 복잡도는 O(N^3)

 

 

 

이상으로 플로이드 워셜 알고리즘에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.