[Graph] Chapter 05. 다익스트라(Dijkstra) 알고리즘

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ed3f5772f67f98efb67841c1795909f85c76211f

다익스트라(Dijkstra) 알고리즘 구현 · developeSHG/Data_Structure-Algorithm@ed3f577

 

 

---

 

 

시작점에서 목적지까지 가는 정점의 간선에 비용이 있다고 가정해보면 적용할 수 있는게 다익스트라 알고리즘이다.

내가 먼저 발견한 순서대로 방문을 하는게 BFS라면, 다익스트라는 인접한 정점을 인지한 후, 방문할 수 있도록 등록은 한다.

근데 각 정점으로 갈 때, 비용은 얼마나 드는지 가중치를 같이 포함해서 기록한다. 그렇게 루프를 돌면서 체크한 다음에, queue를 비웠던 것과 마찬가지로 지금까지 방문한 목록을 스캔하면서 그 중에서 가중치가 가장 낮은 경로를 선택한다. 

 

bfs처럼 먼저 발견한 것을 따라가는 것이 아니고, 추후에도 가중치를 통해 선택할 수 있다. 동작방식은 거의 bfs와 유사하지만 간점마다 다 동일한 cost가 아니라는 차이가 있어서 단순히 queue 하나를 통해 순서대로 예약을 하는 걸로 부족하다. (실제 경로가 효율적인 경로가 아니기 떄문에)

 

코드에 발견 목록으로 Queue가 아닌 List를 사용한 이유는 굳이 선입선출 구조를 안따라도 되기 때문이다. 먼저 찾은 정점이 먼저 방문한다는 보장이 없다.

 

---

 

다익스트라도 BFS와 마찬가지로 딱히 어떠한 목적지를 대상으로 가는 개념은 아니고, 시작점을 기준으로 가장 가까이 있는 정점을 방문한다.

A*와는 다르다. A*는 시작점에서 목적지까지 최대한 목적지를 향해 가려고 시도하는 반면, 다익스트라는 그저 인접한 모든 정점을 가까운 순으로 순회한다는 점이다.

그래서 BFS와 다익스트라는 시작점만 정하고, 목적지는 딱히 의미가 없다. 물론 경우에 따라서 목적지를 두고, 찾은 다음에 빠져나올 수 있게 최적화를 할 순 있겠지만, 불필요하게 엉뚱한 길을 가는 것을 막을 순 없다는 점이다.

 

위의 사실을 인지해서 제일 빠르게 길을 찾을 수 있는 자료구조를 정한다하면 무식하게 모든 정점을 스캔해서 뽑아오는 과정을 최소화해서 효율적으로 만들 수 있을 것이다. 이것을 가장 효율적으로 처리할 수 있는 자료구조가 바로 우선순위 큐다.

우선순위 큐는 그냥 큐와 다르게 넣은 순서대로 데이터가 뽑아 나오는 것이 아니라, 저장하고 있는 데이터 중에서 비용이 가장 낮든 높든 하나의 기준으로 우선 순위를 적용해서 추출할 수 있다.

그래서 다익스트라를 만들 때, 가장 효율적인 자료구조가 우선순위 큐다. 우선 이번 구현은 우선순위 큐를 사용하지 않고 구현했다.

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;

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;
}

void Dijikstra(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);

		// 방문? 더 짧은 경로를 뒤늦게 찾았다면 스킵.
		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;
		}
	}
}

int main()
{
	CreateGraph();

	Dijikstra(0);
}