[그래프] 최단 경로 알고리즘 (Shortest path algorithms)

이번에 알아볼 그래프 알고리즘은 최단 경로 알고리즘(Shortest path algorithms)이다.

 

최소 신장 트리(Minimum spanning tree)는 모든 노드를 최소한의 비용을 들여 연결한 그래프의 모습이라고 했다.

 

이와 다르게 그래프의 최단 경로 알고리즘은 한 노드에서 다른 노드로 이동할 때

 

거치는 간선들의 비용의 총합을 최소한으로 하는 경로를 구한다.

 

대표적으로 다익스트라(Dijkstra) 알고리즘과 플로이드(Floyd) 알고리즘이 있다.

 

각 알고리즘을 알아보기에 앞서 그래프와 최단 경로를 어떤 자료구조를 사용할 것인지 정의하자.

 

그래프를 나타낼 자료구조는 최소 신장 트리에서 소개한 것(weights 변수) 그대로 사용한다.

 

https://izmirprogramming.tistory.com/6

[그래프] 최소 신장 트리 (minimum spanning tree)

 

초기에 weight 변수에 그래프 데이터가 세팅된 것으로 가정한다.

 

최단 경로를 나타낼 자료구조는 3차원 배열을 사용한다.

 

가장 바깥에 있는 배열 인덱스는 최단 경로의 시작 노드를 의미한다.

 

중간에 있는 배열 인덱스는 경로의 최종 목적지 노드를 의미한다.

 

마지막에 있는 배열은 시작 노드로부터 최종 목적지 노드까지의 경로 중에 거치는 노드와 비용을 의미한다.

 

여기까지의 내용을 코드로 표현하면 다음과 같다.

 

struct Cost
{
	std::size_t _nodeNum;
	int _cost;
			
	Cost(std::size_t nodeNum, int cost)
		: _nodeNum(nodeNum), _cost(cost)
	{

	}
};
typedef std::vector<std::vector<std::vector<Cost>>> ShortestPathResult;
ShortestPathResult _result;

 

먼저 다익스트라 알고리즘부터 알아보자.

 

• 다익스트라 알고리즘

한 노드에서 시작하여 다른 나머지 노드들에 대해 최단 경로를 구한다.

 

알고리즘 원리는 탐욕적(Greedy) 방법을 사용한다.

 

탐욕 알고리즘이라고 나중에 이 주제를 가지고 설명하겠지만 간단하게 설명하자면

 

문제를 풀기 위해 작은 문제들의 매 순간 근시안적인 최적해를 구한다.

 

동적 계획법과 다르게 탐욕 알고리즘의 최종해가 항상 최적해가 아님을 주의하자.

 

하지만 어떤 문제는 최적해를 가질 수 있는데 다익스트라 알고리즘이 그렇다.

 

(문제의 성질이나 조건에 따라 결정된다.)

 

이는 추상적으로 방법을 설명한 것이고 구체적인 방법은 다음과 같다.

 

노드들을 대상으로 최단 경로를 구한 노드 집합과 그렇지 못한 집합으로 나눈다.

 

처음에는 시작 노드만 최단 경로를 구한 노드 집합에 포함될 것이다.

 

그리고 최단 경로를 구하지 못한 노드들로부터 하나씩 최단 경로를 구해서

 

최단 경로를 구한 노드 집합으로 추가해 나가는 것이다.

 

여기서 하나씩 노드를 선택하는 우선순위 기준이 위에서 설명한 탐욕적 방법이 적용된다.

 

최단 경로를 구한 노드들 중에 가장 적은 비용으로 연결된

 

최단 경로를 구하지 않은 노드가 높은 우선순위를 갖는다.

 

이제 구체적인 구현 방법을 알아보자.

 

맨 처음에 시작 노드를 정한다.

 

그 시작 노드로부터 다른 나머지 노드들에 대한 각 경로 비용을 저장할 배열을 생성한다.

 

배열의 초깃값으로 시작 노드로부터 다른 나머지 노드들의 초기 비용을 저장한다.

 

아직 시작 노드와 직접적으로 연결된 주변 노드의 비용만 유의미하고

 

나머지 노드에 대한 비용은 무한대(를 의미하는) 값일 것이다.

 

그리고 최단 경로를 구한 노드 집합과 그렇지 않은 집합을 구분하기 위한 배열을 생성한다.

 

여기까지의 내용을 코드로 표현하면 다음과 같다.

 

#define CHECKED 1
#define TO_BE_CHECKED 0

std::vector<Edge> cost;
std::vector<std::size_t> check(_vertexCount, TO_BE_CHECKED);
std::size_t checkCount = 1;

for (std::size_t i = 0; i < _vertexCount; ++i)
{
	Edge edge(vertexNum, i, _weights[vertexNum][i]);
	cost.push_back(edge);
}

check[vertexNum] = CHECKED;

 

Edge라는 자료구조는 간선을 표현한 것으로 최소 신장 트리에서 이미 소개한 적이 있다.

 

vertexNum은 시작 노드를 vertexCount는 노드의 총 개수를 의미한다.

 

시작 노드로부터 다른 노드들로의 최단 경로 비용들을 저장할 배열(cost)과

 

최단 경로를 구한 노드들과 그렇지 못한 노드들의 집합을 구분할 배열(check)을 초기화한다.

 

이제 메인 작업을 알아보자.

 

최단 경로 비용들을 저장한 배열로부터 아직 최단 경로를 구한 노드가 아니면서 비용이 제일 적은 노드를 찾는다.

 

이 작업이 최단 경로를 구한 노드 집합에 있는 노드들 중에 최저의 비용으로 연결된 노드를 찾는 것이다.

 

일단 그 노드를 최단 경로를 구한 집합에 추가한다.

 

그 다음 그 노드에 연결된 아직 최단 경로를 구하지 못한 노드들을 추려낸다.

 

그 노드들에 대한 경로 비용을 이제 알게 되었으니 최단 경로 비용들을 저장한 배열을 갱신한다.

 

비용이 무한대였거나 새로 연결된 노드를 우회했을 때 더 적은 비용이 될 경우 갱신할 것이다.

 

최단 경로 비용을 저장한 배열을 갱신한 후 다시 메인 작업 초반부로 간다.

 

노드를 찾지 못하면 반복을 종료한다.

 

여기까지의 작업을 코드로 표현하면 다음과 같다.

 

int weight;
std::size_t target = 0;
while (checkCount < _vertexCount)
{
	weight = INFINITY_VALUE;
	for (std::size_t i = 0; i < _vertexCount; ++i)
	{
		if (0 < cost[i].value && TO_BE_CHECKED == check[i])
		{
			if (INFINITY_VALUE == weight || cost[i].value < weight)
			{
				weight = cost[i].value;
				target = i;
			}
		}
	}

	if (INFINITY_VALUE == weight)
		break;

	check[target] = CHECKED;
	checkCount++;
	std::vector<Cost>& targetVec = _result[vertexNum][target];
	std::vector<Cost>& fromVec = _result[vertexNum][cost[target].from];
	targetVec.insert(targetVec.begin(), fromVec.begin(), fromVec.end());
	targetVec.push_back(Cost(target, _weights[cost[target].from][target]));

	for (std::size_t i = 0; i < _vertexCount; ++i)
	{
		if (0 < _weights[target][i])
		{
			if (INFINITY_VALUE == cost[i].value || _weights[target][i] + cost[target].value < cost[i].value)
			{
				cost[i].from = target;
				cost[i].value = cost[target].value + _weights[target][i];
			}
		}
	}
}

 

(글자색이 제대로 칠해지지 않는다ㅠㅠ)

 

결과적으로 최단 경로 비용을 저장한 배열에 시작 노드로부터 다른 노드들로의 최단 경로 비용이 저장된다.

 

중간에 있는 vector 관련한 부분은 경로 추적을 위해 작업한 것이다.

 

여기까지가 다익스트라 알고리즘이다.

 

이제 플로이드 알고리즘을 알아보자.

 

• 플로이드 알고리즘

다익스트라 알고리즘은 시작 노드 하나를 정하고 시작하지만

 

플로이드 알고리즘은 모든 노드에 대해 각 최단 경로를 구하는 것이 다른 점이다.

 

그리고 다익스트라 알고리즘과 다르게 구현 방법이 무척 간단하다는 것도 다른 점이다.

 

구현 방법은 모든 노드를 대상으로 3개씩 차례대로 출발, 경유, 도착 노드들을 지정하고

 

출발 노드에서 도착노드로의 기존 비용과 경유 노드를 거쳐서 갔을 때의 비용을 비교 후

 

더 적은 비용으로 갱신하는 것이다.

 

이를 코드로 표현하면 다음과 같다.

 

Graph totalCost = *this;
Graph path = *this;
path.Reset(INFINITY_VALUE);

for (std::size_t i = 0; i < _vertexCount; ++i)
{
	for (std::size_t j = 0; j < _vertexCount; ++j)
	{
		for (std::size_t k = 0; k < _vertexCount; ++k)
		{
			if (INFINITY_VALUE != totalCost[j][i] && INFINITY_VALUE != totalCost[i][k])
			{
				if (INFINITY_VALUE == totalCost[j][k] || totalCost[j][i] + totalCost[i][k] < totalCost[j][k])
				{
					totalCost[j][k] = totalCost[j][i] + totalCost[i][k];
					path[j][k] = i;
				}
			}
		}
	}
}

_result.clear();
_result.resize(_vertexCount);
for (std::size_t t = 0; t < _vertexCount; ++t)
{
	_result[t].resize(_vertexCount);

	for (std::size_t k = 0; k < _vertexCount; ++k)
	{
		setCost(path, t, k, t, k);
	}
}

 

Graph 구조체는 그래프 데이터를 저장할 2차원 배열을 포함하고 있다.

 

모든 노드를 대상으로 각 경로 비용을 저장할 2차원 배열 변수(totalCost)와

 

노드별 경로 추적을 위한 2차원 배열 변수(path)를 생성한다.

 

경로 비용을 저장할 변수의 초깃값은 초기 그래프 데이터가 될 것이다.

 

모든 노드가 바로 연결된 노드에 대해서만 비용이 유의미하고 나머지는 무한대 값을 가질 것이다.

 

그리고 3중 반복문을 볼 수 있다.

 

제일 바깥 반복문(변수 i)은 경유 노드를 의미한다.

 

중간에 있는 반복문(변수 j)은 출발 노드를 의미한다.

 

가장 안쪽 반복문(변수 k)은 도착 노드를 의미한다.

 

이제 앞서 설명한 모든 노드들을 출발, 경유, 도착 노드로 지정하고 매번 비용을 갱신한다는 것을 이해할 것이다.

 

그런데 어떻게 이 작업이 모든 노드들의 최단 경로를 구하는 것일까?

 

필자도 이 부분을 제일 많이 고민했다.

 

일단 경유 노드 위주로 생각해보자.

 

위 코드의 조건문을 보면 출발 노드에서 경유 노드로, 경유 노드에서 도착 노드로의 비용이 유의미할 때만

 

비용을 갱신해주고 있다.

 

즉 출발 노드에서 경유 노드로, 경유 노드에서 도착 노드로 어떤 노드들을 거치는지 모르지만

 

일단 비용이 유의미하다면 기존 비용과 비교 후 갱신한다.

 

이게 처음에는 출발, 경유, 도착 노드 3개만을 가지고 비용 갱신을 시작하지만

 

점점 진행할수록 여러 노드를 경유한 비용을 가지고 갱신하게 된다.

 

경유하는 그 여러 노드들이 앞서 지정한 경유 노드들을 포함하고 있다.

 

이해를 돕기 위해 간단한 예를 들어 보겠다.

 

아래 [그림 1]과 같이 4개의 A, B, C, D 노드가 있다고 하자.

 

우리가 알고 싶은 것은 노드 A에서 노드 D로의 최단 경로 비용이다.

 

첫 번째 경유 노드는 B이고 출발 노드는 A, 도착 노드는 D라고 하자.

 

그럼 [그림 1]의 붉은 색으로 표시한 간선 비용을 계산하여 갱신할 것이다.

 

[그림 1]

 

 

계속 이어서 경유 노드가 B일 때 아래 [그림 2]와 같이 출발 노드가 A, 도착 노드가 C인 경우도 비용을 갱신할 것이다.

 

[그림 2]

 

이제 경유 노드가 C일 때를 보자.

 

출발 노드 A에서 경유 노드 C까지의 최단 경로 비용은 [그림 2]처럼 이미 갱신된 상태이다.

 

즉 25 + 55 비용과 25 + 15 + 5의 비용을 비교하여 더 작은 비용으로 갱신하면 되는 것이다.

 

최종적으로 [그림 3]과 같은 경로의 비용으로 갱신할 것이다.

 

[그림 3]

 

마지막으로 경로 추적 부분을 남겨두고 있다.

 

3중 반복문 내에서 비용을 갱신할 때 경유하는 노드를 path 변수에 저장하는 부분이 있었다.

 

출발 노드에서 도착 노드로의 최단 경로는 경유 노드를 거친다는 정보를 남기고 있다.

 

그렇다면 경로 추적을 위해 출발 노드에서 경유 노드로의, 경유 노드에서 도착 노드로의 경로 중에

 

또 다른 경유 노드가 없을 때까지 추적을 반복하면 최종적으로 경유하는 모든 노드들을 알아낼 수 있다.

 

추적하는 부분이 SetCost 함수인데 구현 코드는 아래와 같다.

 

void Floyd::setCost(Graph& path, std::size_t first, std::size_t last, std::size_t from, std::size_t to)
{
	if (INFINITY_VALUE != path[from][to])
	{
		setCost(path, first, last, from, path[from][to]);
		setCost(path, first, last, path[from][to], to);
	}
	else // nothing between from and to
	{
		if(INFINITY_VALUE != _weights[from][to])
			_result[first][last].push_back(Cost(to, _weights[from][to]));
	}
}

 

이상으로 플로이드 알고리즘을 알아 보았다.

 

플로이드 알고리즘 같은 경우 다소 헷갈릴 수 있으므로 깊게 고민해 볼 필요가 있다.