최소신장트리 최단경로 차이 - choesosinjangteuli choedangyeonglo chai

Question

- 이전 글: [DS] Graph 개념과 탐색방법

목차 Show

Dijkstra (다익스트라)
[그래프] 최단 경로 트리 알고리즘 vs 최소 신장 트리 알고리즘

3. MST (Minimum Spanning Tree)

최소 신장 트리 (MST)는 그래프의 최소 연결 트리를 의미한다. 최소 연결 트리란 edge의 weight가 최소인 spanning tree를 말한다. spanning tree는 그래프의 모든 정점을 cycle 없이 연결한 형태를 말한다.

최소 신장 트리는 N개의 정점과 N-1개의 간선으로 연결되어 있으며 가중치의 합이 신장 트리 중에 최소인 값이 되어야 하기 때문에 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻을 수 없다. MST를 찾는 대표적인 방법으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다.

1) Kruskal algorithm

greedy 한 방법으로 간선을 선택하여서 MST를 구하는 방법이다. 최소 비용의 간선으로 이루어진 MST를 찾기 위해서 간선을 오름차순으로 정렬하여 가중치가 작은 간선부터 순서대로 선택을 한다. 이때 사이클이 생기지 않도록 확인하면서 선택해야한다.

- 과정

그래프의 간선을 가중치의 오름차순으로 정렬한다.
정렬된 간선들을 순서대로 선택한다.
선택한 간선이 사이클을 이루는지 확인한다.
- 각 정점에 Index를 부여하고 정점들이 연결될 때마다 두 정점의 index를 통일해서 각각의 연결관계를 관리한다.
- 이 방법으로 index가 같은 경우 같은 서브트리에 포함되어있기 때문에 사이클을 이룬다는 것을 파악할 수 있다.
사이클을 이루지 않는 경우 MST에 해당 간선 정보를 추가한다.

- 시간복잡도

Edge의 weight를 기준으로 정렬: O(E log E)
cycle 생성 여부 확인 및 index 통일: O(E + V log V)
time complexity: O(E log E)

2) Prim algorithm

Kruskal 알고리즘이 간선을 중심으로 알고리즘을 진행한다면 Prim 알고리즘은 노드에 집중해서 알고리즘을 진행한다. 초기 source 정점에서부터 인접한 정점들을 확인해서 가장 작은 가중치의 간선을 통해 연결되는 정점을 추가하는 방법을 반복한다. 한마디로 이미 MST 집합에 추가된 정점들로부터 인접한 정점들 중 가장 가까운 정점을 추가하는 방식으로 알고리즘을 진행한다.

- 과정

시작 정점을 MST 집합에 포함한다.
MST 집합에 포함된 정점들에 대해서 인접한 정점들 중 최소 간선으로 연결된 정점을 선택하여 트리에 추가한다.
위의 과정을 MST가 N-1 개의 간선을 가질 때까지 반복한다.

- 시간 복잡도: O(E log V)

4. Shortest path problem

최단 경로 문제는 그래프 상의 두 정점의 사이를 잇는 최단 경로를 찾는 문제이다. 최단 경로를 찾는 문제는 경로를 찾는 정점의 개수에 따라서 문제의 유형과 풀이방법이 달라진다. 문제의 유형은 다음과 같다.

단일 노드 - 단일 노드 문제: 단일 정점에서 다른 한 정점으로의 최단 경로를 찾는 문제이다.
단일 노드 - 전체 노드 문제: 단일 정점에서 다른 모든 정점으로의 최단 경로를 찾는 문제이다.
모든 노드 간의 경로 문제: 그래프에 존재하는 모든 정점들 간의 최단 경로를 찾는 문제이다.

1) Dijkstra Algorithm

다익스트라 알고리즘은 두 정점 간의 가장 짧은 경로를 찾는 알고리즘이다. 보통 알고리즘을 반복하여서 한 정점으로부터 나머지 정점들로의 최단 거리를 구하는데 사용하는 알고리즘이다. 우선순위 큐를 사용해서 가장 낮은 가중치를 가진 방문하지 않는 정점을 찾고 방문하지 않은 나머지 정점과의 거리를 계산하여 비교하는 방법으로 구현한다.

2) Bellman-Ford Algorithm

벨만 포드 알고리즘은 가중치가 음인 그래프에서 최단 거리를 찾는데 사용하는 알고리즘이다. 다익스트라보다 시간복잡도가 크지만 음의 가중치가 있는 그래프에서 최단거리를 구하기 위해서는 벨만 포드 알고리즘을 사용한다.

3) Floyd-Warshall Algorithm

모든 정점 간의 최단 경로를 찾는데 사용하는 알고리즘이다. 그래프의 가중치가 음이든 양이든 상관없이 사용할 수 있는 알고리즘이다. 두 정점의 사이에 대해서 다른 모든 정점을 경유하는 경로를 비교하여 최단 거리를 찾는 방법으로 진행된다.

[reference]

- https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io

- https://ko.wikipedia.org/wiki/최단_경로_문제

최단 경로 문제 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 그래프 이론에서 최단 경로 문제란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로

ko.wikipedia.org

jook1356.log

jook1356·2022년 9월 29일

그래프

0

최단경로

여러 정점들을 거쳐 돌아가더라도 거리(가중치)가 짧으면 된다.
그래프가 순환이 가능하게 연결될 수 있다. (말하자면 도형이 된다.)

최소신장트리(MST)

돌아가는 것을 고려하지 않고 해당 정점에서 인접 정점들중 거리(가중치)가 가장 짧은 것을 고른다.
그래프가 순환이 되는 것을 허용하지 않는다. (멍게식 연결..?)

김동주

편안한 마음으로

이전 포스트

Dijkstra (다익스트라)

다음 포스트

클랜원

0개의 댓글

알고리즘

[그래프] 최단 경로 트리 알고리즘 vs 최소 신장 트리 알고리즘

yoosojeong1107 2022. 5. 17. 21:43

다익스트라, 플로이드: 최단 경로 트리
프림: 최소 신장 트리

최단 경로 트리 알고리즘과 최소 신장 트리 알고리즘은 서로를 보장하지 않음
따라서 위의 사진을 보면 프림 알고리즘이 0->2의 비용이 더 나가는 것을 볼 수 있음 (최단 경로를 보장하지 않기 때문이다.)

최소 신장 트리 알고리즘에는 모든 정점을 연결하는데 의의가 있다.

다익스트라와 플로이드의 차이는
다익스트라 : 시작 정점 to 모든 최단 경로
플로이드 : 모든 정점 to 모든 정점 최단경로

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

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

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

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

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

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

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

https://izmirprogramming.tistory.com/6

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

이번에는 그래프의 최소 신장 트리(minimum spanning tree)를 알아보자. 최소 신장 트리가 무엇일까? 먼저 그래프는 익히 알고 있을 것이다. 그래프는 노드와 간선으로 구성된다. 지하철 노선도로 비유하자면 지하..

izmirprogramming.tistory.com

초기에 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]));
	}
}

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

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

크루스칼 알고리즘 다익스트라 알고리즘