'최단거리'에 해당되는 글 2건

플로이드(Floyd) 알고리즘

이번에는 조금 더 간단하게 최단거리를 구할 수 있는 알고리즘을 소개합니다.

다익스트라 알고리즘은 한 시작점에서 다른 정점까지의 최단 거리를 구하는데 반해 플로이드 알고리즘은 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구할 수 있습니다!

단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작합니다.

경유점

어떤 정점 a와 b가 연결되어 있다고 할때 이 정점 사이에 c가 있다고 하지요. a와 b로 연결되어 있는 간선의 비용이 5라고 하구요.

하지만 a와 c의 비용은 2, b와 c의 비용은 2라고 한다면 a와 b로 가는데 c를 거쳐가는 것이 더 효율적이라는 것을 알 수 있습니다. a-c-b의 비용은 4이기 때문에 a-b의 비용 5보다 비용이 더 적습니다.

c와 같이 경로가 거쳐가는 정점이 경유점이라고 하지요.

플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택하게 됩니다.

구현

아래와 같은 그래프가 있는데 모든 쌍의 최단거리는 어떻게 될까요?

1-4까지의 최단 거리?

0-3까지의 최단 거리?

이제 본격적으로 구현해보도록 합시다.

그래프의 초기화

위의 그래프를 우선 배열로 구현해야합니다. 조건이 있는데, 초기에 직접적으로 연결되어 있지 않은 경로는 아주 큰 값으로 설정해야한다는 것이죠. 그리고 자기 자신까지의 비용은 0으로 만들어 줍니다.

플로이드 알고리즘 적용

이제 플로이드 알고리즘만 적용시켜주면 되지요.

시작점은 i, 끝점을 j, 경유점을 k라고 했을때 구하는 식은 다음과 같습니다.

이 경유점 k를 지나는 모든 i, j에 대해서 확인해주면 됩니다.

adj[i][j]와 adj[i][k]+adj[k][j] 중 항상 작은 값만을 갖게 되므로 직접적으로 연결이 되지 않는 간선은 INF로 처음에 초기화 한 이유를 아시겠어요?

만일 경유점 k가 0이라고 할때 adj[1][2] = MIN(adj[1][2], adj[1][0] + adj[0][2]) = MIN( INF, 5) = 5 가 됩니다. 결국 1-2까지의 경로는 5로 더 작은 값이 됨을 알 수 있죠.

그 후 경유점이 k=2가 되었다고 할때 adj[1][3] = MIN(adj[1][3], adj[1][2] + adj[2][3]) = MIN(INF, 6) = 6이 됩니다. 왜냐면 방금전 adj[1][2]를 구해냈기 때문이지요. 그래서 1-3까지의 비용은 6이 되는 것을 알 수 있습니다.

이렇게 모든 경유점을 확인하면서 비용이 작은 값만을 선택합니다.

이제 전체 코드를 보면서 결과를 확인해보세요.

#include <stdio.h>
#define MAX_V 10
#define MIN(a,b) a<b ? a:b
#define INF 987654321
int V,E;
int adj[MAX_V][MAX_V];
void initAdj() {
	int i, j;
	for (i = 0; i < V; i++)
		for (j = 0; j < V; j++) {
			adj[i][j] = INF;
			if (i == j)adj[i][j] = 0;
		}
}
void floyd() {
	int k,j,i;
	
	for (k = 0; k < V; k++)
		for (i = 0; i < V; i++)
			for (j = 0; j < V; j++)
				adj[i][j] = MIN(adj[i][j], adj[i][k] + adj[k][j]);
}
int main() {
	int i, j;
	printf("정점 개수:");
	scanf("%d", &V);
	printf("간선 개수:");
	scanf("%d", &E);

	initAdj();

	printf("정점 연결( 정점1 정점2 비용) \n");
	for (i = 0; i < E; i++) {
		int v1, v2, cost;
		scanf("%d %d %d", &v1, &v2, &cost);
		adj[v1][v2] = adj[v2][v1] = cost;
	}


	floyd();

	for (i = 0; i < V; i++) {
		for (j = 0; j < V; j++)
			printf("%d~%d까지의 최단거리:%d\n", i, j, adj[i][j]);
		printf("\n\n");
	}
}

경유점 k의 순서가 꼭 0부터 V까지 순차적일 필요는 없습니다. 경유점을 어느 순서로 해도 상관이 없다는 것이죠.

복잡도

위 코드의 시간복잡도는 O(V^3)이 되고 공간복잡도는 O(V^2)가 됩니다. 플로이드 알고리즘은 V가 작고 모든 정점의 최단 거리를 구할때 아주 유용하고 쉽게 구현할 수 있기 때문에 기억해둘만한 가치가 충분히 있습니다.

다익스트라 알고리즘 (Dijkstra Algorithm)

최단거리를 구하는 데에는 꽤 여러가지 알고리즘이 존재합니다. 그 중에서 가장 유명한 알고리즘, 다익스트라 알고리즘에 대해서 알아보도록 하겠습니다.

다익스트라 알고리즘은 무엇일까요?

그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 것이 이 알고리즘입니다. 

우선 아래와 같은 그래프가 있다고 가정해볼게요.

정점 0에서 모든 정점까지의 최단거리는 어떻게 될까요?

0번에서부터 5번 정점 중 임의의 i까지 최단 거리를 dist[i]라고 할때

가 됩니다.

이와 같이 어떤 시작점을 정해서 그 정점부터 다른 정점까지의 최단거리를 구하는 알고리즘이 바로 단일 시작점 알고리즘이고, 대표적인 알고리즘이 바로 다익스트라 알고리즘입니다.

BFS 최단거리 기반

이 알고리즘은 최단 거리를 구하는 것이기 때문에 BFS를 기반으로 움직이는데요. BFS는 자료구조에서 큐를 썼었죠? 따라서 다익스트라 알고리즘 역시 큐를 사용하여 구현할 수 있다는 사실을 알아두세요.

주의 사항은 위의 그래프가 나타내는 것처럼 음수간선이 있으면 다익스트라 알고리즘을 쓸 수가 없어요.

다익스트라 구현 (C++)

코드로 다익스트라 알고리즘을 살펴본 후 설명하도록 하겠습니다.

#include <vector>
#include <iostream>
#include <queue>

#define MAX_V 100
#define INF 99999999
using namespace std;


vector<pair<int, int> > adj[100];
vector<int> dijkstra(int start, int V) {
	vector<int> dist(V, INF);
	dist[start] = 0;
	priority_queue<pair<int, int> > q;
	q.push(make_pair(0, start));

	while (!q.empty()) {
		int cost = -q.top().first;
		int from = q.top().second;
		q.pop();

		if (dist[from] < cost) continue;

		for (int i = 0; i < adj[from].size(); i++) {
			int to = adj[from][i].first;
			int distFromTo = cost + adj[from][i].second;
			if (distFromTo < dist[to] ) {
				dist[to] = distFromTo;
				q.push(make_pair(-distFromTo, to));
			}
		}
	}
	return dist;
}

int main(int argc, char **argv)
{
	int E, V;
	printf("[input] vertex edge :");
	scanf("%d %d", &V, &E);

	
	for (int i = 0; i < E; i++) {
		printf("[input] from to cost :");
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		adj[from].push_back(make_pair(to, cost));
		adj[to].push_back(make_pair(from, cost));
	}

	printf("===dijkstra===\n");
	vector<int> dist = dijkstra(0, V);
	for (int i = 0; i < V; i++) {
		printf("from 0 to %d : %d\n", i, dist[i]);
	}
	return 0;
}

우선 입력을 받습니다. 위의 그래프 모양 그대로 입력을 받습니다. 위의 그래프를 조금 더 편하게 입력받으려면 아래의 input을 복사해서 붙여넣으세요.

이후 dijkstra가 어떻게 동작하는 지 그림을 보며 살펴보도록 합시다.

우선 우리가 반환한 dist의 벡터 사이즈를 V의 크기(정점의 개수)로 정하고 그 값을 아주 큰 값으로 설정합니다.

자기 자신과의 거리는 0이므로 dist[start]는 0으로 셋팅합니다.

여기서는 priority queue를 사용하는데요. 그 이유는 정점으로부터 가장 작은 값으로 연결되어 있는 정점을 꺼내는 것이 더 효율적이니까 그렇습니다.

또한 priority queue는 pair를 통해서 우선 순위를 정할때 첫번째 요소를 기준으로 가장 큰 값을 먼저 꺼내옵니다. 그래서 첫번째 요소를 거리, 그것도 -를 붙여서 넣어주면 값이 큰 간선으로 연결된 정점이 더 나중에 나오게 되는 것이죠.

그래서 꺼내올때 -를 붙여서 꺼내오고 -를 붙여서 집어 넣습니다.

이제 그림으로 더 쉽게 보도록 합시다.

우선 초기상태는 자기 자신의 정점을 우선순위 큐에 push하며 그 거리는 0이 됩니다. while루프를 돌기 전의 모습입니다. 

그 후 첫 while 루프를 돌면서 큐에 저장된 (0,0)을 가져옵니다. 0은 dist[0]보다 작지 않기 때문에 if문에 걸리지 않고 for루프를 돌게 됩니다. 주변에 가장 작은 값으로 연결된 정점은 2, 1, 3이지요. 그래서 그에 대응되는 거리 2, 3, 5와 함께 우선 순위 큐에 저장합니다. 

하지만 우선순위 큐는 큰 값이 먼저 선정되기 때문에 음수를 붙여서 -2,-3,-5로 바꾸어서 넣어줍니다.

** 아래 그림에서 잘못된 것이 있는데 우선순위 큐에 푸시되는 값은 (-2,2) (-3,1) (-5,3)인것으로 정정해주세요. 죄송해요.

우선순위 큐에서 2를 꺼내올때 이미 dist[2]는 2로, dist[2]보다 2가 더 작지 않으므로 if 조건문에 걸려 continue됩니다.

이 후 (-3, 1)을 꺼내옵니다. 정점 1에서 연결된 정점 중 가장 가까운 정점은 4입니다. 그렇기 때문에 dist[4]를 12로 수정하고 이 정보를 우선순위 큐에 저장합니다.

이제 (-5,3)을 꺼내올 차례이군요. dist[3]은 5이고, 큐에서 꺼내온 값 역시 5이므로 if문에 걸리지 않고 for루프를 돕니다. 이제 3에 연결되어 있는 정점은 4로 연결된 cost가 1인 간선입니다. 그래서 그전에 있던 dist[3]과 4로 연결된 간선의 cost 1을 더한 값(6)과 dist[4]와 연결된 값과 비교해보니 6이 더 작으므로 dist[4]=6으로 갱신하고 (-6,4)를 큐에 집어 넣습니다.

여기서 우선순위 큐를 사용하는 이유가 나옵니다. 만일 순서를 고려하지 않고 (-5, 3)이 큐에 맨 끝에 위치해있다면 이러한 갱신을 맨끝에 하게 되어 for루프를 돌게 되는 시간적인 낭비가 있게 되는 겁니다. 

그렇기 때문에 가장 비용이 낮은 것이 먼저 나오는 것이 유리하다는 것이죠.

다음 (-15,4)는 cost가 15이기 때문에 if조건에 걸려 continue됩니다. 

남은 (-6, 4)를 꺼내오게 되면 if조건문에 걸리지 않고 for루프를 돌아요. 4와 연결된 정점 5까지의 비용은 dist[4]와 3을 더한 9가 됩니다. 왜냐하면 dist[5]는 아주 큰 값이기 때문에 6이 더 작잖아요?

그 후 5와 연결된 간선의 정보를 큐에 저장합니다.

이제 마지막 (-9, 5)를 꺼내오는데, 이미 dist[5]=9이므로 if 조건에 걸려 continue됩니다. 이 후에는 큐가 비었으므로 while문을 탈출하게 되지요.

이제 모든 거리를 구했습니다.

코드에서는 0을 기준으로 구했는데 코드를 바꾸어서 1부터 시작해서 최단거리를 구해보세요. 그리고 비교해보세요.