다익스트라 알고리즘

 다익스트라 알고리즘은 대표적인 최단 경로 탐색을 하는 알고리즘입니다. 다익스트라 알고리즘은 출발 정점을 시작으로 다른 모든 정점으로 향하는 모든 최단 경로 및 비용을 알려줍니다. 하지만 간선의 비용은 음수가 될 수 없습니다. 

 

 다익스트라 알고리즘은 하나의 정점에 대한 최단 경로를 알기 위해서 해당 경로에 향하기까지의 모든 정점들에 대해 최단 경로들을 구해야 합니다. 그렇기 때문에 최단 경로를 구하면서 이전에 구해놓은 최단 거리의 정보를 사용하게 됩니다. 처음 정점에서 간선을 통해 연결된 정점에 대한 최단 거리를 구하고, 방문하지 않은 정점들 중에서 가장 작은 거리(비용)을 가진 정점에 대해서 탐색을 하게됩니다. 첫 정점과 마찬가지로 연결된 간선들에 대해서 최단 거리를 구하게 되는데, 도착 정점이 이미 가지고 있던 최단 비용보다 이번 탐색을 통해 구한 새로운 경로의 비용이 더 적은 경우, 도착 정점에 대한 최단 경로와 비용을 갱신하게 됩니다. 해당 방식으로 모든 정점에 대한 탐색을 마치게 되면 최종적으로 출발 정점에서 모든 정점에 대한 최단 거리(비용)을 구하게 되는 것이 다익스트라 알고리즘의 방식입니다.

 

정리를 하면,

1. 출발 정점을 지정한다. (연결된 정점들에 대한 최단 비용을 갱신한다.)

2. 탐색하지 않은 정점 중, 가장 적은 비용을 가진 정점을 고른다.

3. 해당 정점(V1)과 연결된 정점들(V2)을 구하고 'V2가 이미 가지고 있는 최단 비용'보다 'V1을 거쳐 V2로 가는 비용'이 더 작다면 V2에 대한 최단 비용을 갱신한다.

4. 모든 정점에 대한 탐색을 마칠 때까지, 2~3번의 과정을 반복한다.

 

해당 내용을 코드로 살펴보도록 하겠습니다.

 

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(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> discover;		 // 발견 목록
	vector<int> best(6, INT32_MAX);  // 각 정점별로 지금까지 발견한 최소 거리

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

	while (discover.empty() == false)
	{
		// 검색이 필요한 Vertex 중에서 가장 작은 값을 가진 후보를 찾는다.
		list<VertexCost>::iterator bestIt;
		int bestCost = INT32_MAX;

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

		int cost = bestIt->cost;
		here = bestIt->vertex;
		discover.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;

			best[there] = nextCost;
			cout << there << endl;
			discover.push_back(VertexCost{ there, nextCost });
		}
	}
}

이상으로 다익스트라 알고리즘에 대한 설명을 마무리하겠습니다. 포바~!