[알고리즘] 플로이드 와샬 - 최단경로 구하기(Floyd-Warshall), C/C++

그래프 자료구조에서 최단 경로, 최소 비용를 구해야 하는 알고리즘은
너비 우선 탐색(BFS), 다익스트라, 벨만-포드, 플로이드 워샬 이 있습니다.

 

1. 플로이드 와샬(Floyd-Warshall) 알고리즘이란?

플로이드 와샬은 그래프 자료구조에서 노드와 가중치가 있는 간선이 존재할 때 모든 정점간의 최소 비용을 구할 수 있는 그래프 탐색 알고리즘 입니다. 

 

 

5개의 노드와 6개의 간선이 존재하는 그래프 예시를 들겠습니다. 여기서 간선의 방향은 단지 갈수 있냐, 없냐를 결정지을 뿐 중요하지 않습니다.

BFS나 다익스트라 같은 탐색 기법은 특정 노드끼리의 최소 비용만 구하면 됩니다. 즉 탐색을 시작하는 시작 노드가 정해져 있는 경우에 해당됩니다. 하지만 플로이드 와샬은 모든 노드간의 최소 비용을 구할 수 있습니다.

 

 

1 -> 2 최소 비용: 1

1 -> 3 최소 비용: 3

1 -> 4 최소 비용: 12

1 -> 5 최소 비용: 9

....

 

최단 거리를 구할 때, 특정 노드를 가운데에 끼어서 거치는 경우를 체크해보는 방식으로 확인해 보는게 플로이드 와샬 기법의 핵심입니다.

위의 그래프를 예로 들어, 1 -> 3 최소 비용을 탐색해본다고 가정해 봅시다. 1 -> 3으로 이어진 간선 하나를 선택하게 되면 가중치 5을 소비하게 되지만, 1 -> 2 -> 3의 경로를 거치게 된다면 도합 3의 가중치를 소비하게 되는 거죠. 즉 1 -> 3을 거칠 때, 곧바로 1에서 3을 간다기 보다는 2 노드를 거쳐 가는게 최소 비용임을 알 수 있습니다.

 

 

2. 플로이드 와샬 구현하기

다음 그래프를 예시로 플로이드 와샬 알고리즘을 구현하겠습니다.

1) 그래프 만들기

#include <cstdio>
#include <vector>
using namespace std;

typedef struct {
	int node, weight;
}INFO;
vector <INFO> v[6];

void MakeGraph() {
	// 노드 1에 연결된 정보
	v[1].push_back({ 2, 1 });
	v[1].push_back({ 3, 5 });
	v[1].push_back({ 5, 9 });
	// 노드 2에 연결된 정보
	v[2].push_back({ 1, 1 });
	v[2].push_back({ 3, 2 });
	// 노드 3에 연결된 정보
	v[3].push_back({ 1, 5 });
	v[3].push_back({ 2, 2 });
	v[3].push_back({ 5, 2 });
	// 노드 4에 연결된 정보
	v[4].push_back({ 5, 3 });
	// 노드 5에 연결된 정보
	v[5].push_back({ 1, 9 });
	v[5].push_back({ 3, 2 });
	v[5].push_back({ 4, 3 });
}

int main(void) {
	MakeGraph();
}

 

 

2) 최소 비용의 합 초기화

노드A -> 노드B 이동할 때의 최소 비용의 합을 담을 2차원 배열이 필요합니다. 그리고 최초 그래프가 주어졌을 때 주어진 간선 및 가중치 정보를 활용해 2차원 배열의 값을 채워 줍니다. 여기서 가장 큰 값을 10억이라고 가정하고 INF로 정의했습니다.(왜 10억인지는 있다가!)

 

#define INF 1000000000

int ArrayFY[6][6];

void InitFY() {
	// (1) 모든 값을 0 혹은 INF로 초기화
	for (int i = 1; i <= 5; i++) {
		for (int j = 1; j <= 5; j++) {
			if (i == j) ArrayFY[i][j] = 0;
			else ArrayFY[i][j] = INF;
		}
	}

	// (2) 그래프에 그려진 간선 정보 넣기
	for (int i = 1; i <= 5; i++) {
		for (int j = 0; j < v[i].size(); j++) {
			int nextNode = v[i][j].node;
			int weight = v[i][j].weight;

			ArrayFY[i][nextNode] = weight;
		}
	}
}

int main(void) {
	MakeGraph();
	InitFY();
}

 

 

3) Floyd Warshall 구현하기

#include <algorithm>

void FloydWarshall() {

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

int main(void) {
	MakeGraph();
	InitFY();
	FloydWarshall();
}

앞서 말했다 시피 플로이드 와샬 알고리즘의 핵심은 특정 노드를 가운데에 끼어서 거치는 경우를 체크해야 한다는 점 입니다. 1 -> 2를 이동하는 최단경로를 구할 때, 그 사이에 노드를 끼워서 계산해보는 방식이죠.

노드를 끼워서 가는게 최소냐, 아니면 그냥 원래 들고 있던 값이 최소냐를 min 함수로 판단하도록 했습니다. 앞서 ArrayFY 배열의 최대 값을 10억으로 초기화한다고 앞에 말씀드렸습니다. 왜냐면, ArrayFY[i][k] + ArrayFY[k][j] 결과가 INT 범위를 벗어나 오버플로우가 발생할 수 있기 때문입니다(INT 최대 값: 2147483647)

 

 

4) 최종 소스

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1000000000
typedef struct {
	int node, weight;
}INFO;
vector <INFO> v[6];
int ArrayFY[6][6];

void InitFY() {
	// (1) 모든 값을 0 혹은 INF로 초기화
	for (int i = 1; i <= 5; i++) {
		for (int j = 1; j <= 5; j++) {
			if (i == j) ArrayFY[i][j] = 0;
			else ArrayFY[i][j] = INF;
		}
	}

	// (2) 그래프에 그려진 간선 정보 넣기
	for (int i = 1; i <= 5; i++) {
		for (int j = 0; j < v[i].size(); j++) {
			int nextNode = v[i][j].node;
			int weight = v[i][j].weight;

			ArrayFY[i][nextNode] = weight;
		}
	}
}
void MakeGraph() {
	// 노드 1에 연결된 정보
	v[1].push_back({ 2, 1 });
	v[1].push_back({ 3, 5 });
	v[1].push_back({ 5, 9 });
	// 노드 2에 연결된 정보
	v[2].push_back({ 1, 1 });
	v[2].push_back({ 3, 2 });
	// 노드 3에 연결된 정보
	v[3].push_back({ 1, 5 });
	v[3].push_back({ 2, 2 });
	v[3].push_back({ 5, 2 });
	// 노드 4에 연결된 정보
	v[4].push_back({ 5, 3 });
	// 노드 5에 연결된 정보
	v[5].push_back({ 1, 9 });
	v[5].push_back({ 3, 2 });
	v[5].push_back({ 4, 3 });
}
void FloydWarshall() {

	for (int k = 1; k <= 5; k++) {
		for (int i = 1; i <= 5; i++) {
			for (int j = 1; j <= 5; j++) {
				ArrayFY[i][j] = min(ArrayFY[i][j], ArrayFY[i][k] + ArrayFY[k][j]);
			}
		}
	}
}
void show() {
	for (int i = 1; i <= 5; i++) {
		for (int j = 1; j <= 5; j++) {
			if (ArrayFY[i][j] == INF) printf("%5s ", "INF");
			else printf("%5d ", ArrayFY[i][j]);
		}
		printf("\n");
	}
}
int main(void) {
	MakeGraph();
	InitFY();
	FloydWarshall();
	show();
}

 

 

5) 결과

 

 

 

3. 플로이드 와샬 정리

1) 3중 for문을 탐색하기 때문에 시간 복잡도는 O(V³) 입니다.

2) i=1, j=1부터 i=N, j=N까지 Bottom-Up으로 탐색하며, 동시에 Memoization을 수행하기에 DP 탐색과 유사합니다.