[C++ 자/알 Note] 다익스트라 알고리즘

주의사항

- BFS의 한계

가중치 그래프 적용이 불가능하다

예를 들어, 미로에서 대각선 이동이 가능한 경우에는

가중치가 필요하고 이를 구현하기는 불가능하다

 

- Dijkstra 한계 1

BFS처럼 결국 완전탐색으로 동작한다

 

- Dijkstra 한계 2

아래에서 Dijkstra를 구현하는 방식은 list를 활용한다

모든 노드를 다 스캔해서 가장 최적을 고르는 방식을 채택한다

그런데 우선순위 큐를 활용하면 이를 해결할 수 있다

 

- Dijkstra 준비물

Vertex와 Cost를 합친 VertexCost 구조체를 생성한다

map을 사용해서 생성하는 방법도 가능하다

그리고

발견목록을 저장할 discovered

가장 최소거리를 저장할 best

경로저장을 위한 parent가 필요하다

 

- Dijkstra 내부 동작

BFS와 비슷한 느낌으로 동작된다

list가 빌 때까지 반복해서 돌면서

list를 비우면서 list의 자식들을 발견 list에 넣는다

 

반복문 안에서의 단계를 이해하기 쉽게 나눈다면

1) 제일 좋은 후보 찾기

지금 본인 정점을 발견하는 방식(루트)이

discovered에 push_back 되어있기 때문에

가장 코스트가 낮은 것을 찾는 작업을 한다

 

2) erase

다 찾고나면, 해당 정보를 복사해 놓고

list에서 erase로 지워준다

 

3) best[here]과의 비교

후보 하나를 데리고 왔는데

해당 후보보다 이미 좋은 best가 있다면

사실 본인이 들어갈 이유는 없다

 

4) 방문

연결되지 않은 경우와

더 좋은 경로가 이미 존재하는 경우를 제외하고

발견한 모든 것들을 다 push_back 해준다

 

다익스트라 알고리즘 코드

- 준비물 및 그래프 생성

struct Vertex
{
	// int data;
};

vector<Vertex> vertices;
vector<vector<int>> adjacent; // 인접 행렬

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));

	adjacent[0][1] = 15;
	adjacent[0][3] = 35;
	adjacent[1][0] = 15;
	adjacent[1][2] = 5;
	adjacent[1][3] = 10;
	adjacent[3][4] = 5;
	adjacent[5][4] = 5;
}

 

- Dijkstra 알고리즘 구현

void Dijkstra(int here)
{
	struct VertexCost
	{
		int vertex;
		int cost;
	};

	list<VertexCost> discovered;// 발견 목록
	vector<int> best(6, INT32_MAX);// 각 정점별로 지금까지 발견한 최소 거리
	vector<int> parent(6, -1);// 경로저장을 위한 부모

	discovered.push_back(VertexCost{ here, 0 });
	best[here] = 0;
	parent[here] = here;

	while (discovered.empty() == false)
	{
		// 제일 좋은 후보를 찾는다
		list<VertexCost>::iterator bestIt;
		int bestCost = INT32_MAX;

		for (auto it = discovered.begin(); it != discovered.end(); it++)
		{
			if (it->cost < bestCost)
			{
				bestCost = it->cost;
				bestIt = it;
			}
		}

		int cost = bestIt->cost;
		here = bestIt->vertex;
		discovered.erase(bestIt);

		// 위를 통해 찾은 후보가 best보다 큰 경우는 필요없음
		if (best[here] < cost)
			continue;

		// 방문
		for (int there = 0; there < 6; there++)
		{
			// 연결되지 않은 경우 제외
			if (adjacent[here][there] == -1)
				continue;

			// 더 좋은 경로를 과거에 찾았으면 제외
			int nextCost = best[here] + adjacent[here][there];
			if (nextCost >= best[there])
				continue;

			discovered.push_back(VertexCost{ there, nextCost });// 발견한 것들을 다 넣어주는 방식
			best[there] = nextCost;
			parent[there] = here;
		}
	}
}