2-5. 다익스트라(Dijkstra) 알고리즘

0. BFS의 한계

(1) 연결된 간선들을 동일한 비용이라고 가정 -> 거리에 따른 가중치가 없음

(2) 인접한 정점을 모두 예약, 방문하기 때문에 낭비가 있음

<-> 다익스트라 알고리즘에서는 가중치를 비교하므로 비용이 크면 방문하지 않음

 

1. 다익스트라(Dijkstra) 알고리즘

시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘.

 

(1) 시작 정점에서 가장 가까운 정점을 선택

(2) 다른 노드로 가는 최단 거리 계산

(3) 방문하지 않은 정점에서 최단 거리를 가지는 정점 선택

(4) 해당 정점을 거쳐 다른 정점으로 가는 경로의 최단 거리 계산 ... (반복)

- 거리는 다음 정점(자식)을 기준으로 이전 정점(부모)의 가중치와 그 다음 정점의 가중치를 더한 값이다.

 

2. 가중치 그래프 구현

struct Vertex
{

};

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

void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1)); // 6x6 2차원 배열

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

 

3. 다익스타 알고리즘 구현

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

	list<VertexCost> discovered; // 발견 목록, 왕복이 가능하기 때문에 큐가 아닌 리스트로 구현
	vector<int> best(6, INT32_MAX); // 정점별 지금까지 발견한 최소 거리

	discovered.push_back(VertexCost{ here, 0 }); // 시작점 초기화
	best[here] = 0;

	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) // cost가 작은 것을 bestCost에 저장(순위표 처럼)
			{
				bestCost = it->cost;
				bestIt = it;
			}
		}

		int cost = bestIt->cost; // 최소 경로의 값을 꺼냄
		here = bestIt->vertex; // here에 반복자가 가리키는 정점을 대입
		discovered.erase(bestIt);

		// 더 짧은 경로를 뒤늦게 찾았다면 스킵
		if (best[here] < cost)
			continue;

		// 인접한 정점들 방문(-1이 아닌 배열들)

		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;

			discovered.push_back(VertexCost{ there, nextCost });
		}
	}
}

(1) list vs queue에서 list를 사용하는 이유?

- 중간 삽입 / 삭제의 용이성

- 우선순위 큐를 구현하기 쉬움

- 작은 규모 그래프에서 효율적으로 작동

 

(2) 최단 거리(최단 경로) 찾기

최단 거리를 갖는 정점을 가리키는 반복자, bestIt와 그 최단 거리 값을 갖는 bestCost를 사용한다.

반복자로 리스트의 처음부터 끝까지 훑고, 탐색된 정점들 중에서 최단 거리인 점과 최단 거리를 bestIt, bestCost에 기록한다.

최단 거리로 이동하기 위해 cost에 최단 거리 bestCost를 대입해주고, 그 정점을 here에 대입(방문하는 과정)한다.

그리고 list에서 그 정점을 제거한다.

이후에 중복 방문을 방지하기 위해서 더 짧은 경로를 늦게 찾아준 경우 continue를 해준다.

그리고 인접 여부를 파악해서 다음 인접한 정점의 가중치를 계산, 방문 목록인 list에 push back한다.

 

(3) 경로 추적

void Dijikstra(int here)
{ // ~~~~
	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;

		for (int there = 0; there < 6; there++)
		{ //~~~~
			// 더 좋은 경로를 과거에 찾았다면 스킵
			if (nextCost >= best[there])
				continue;

			best[there] = nextCost;
			parent[there] = here;

parent 값을 통해 이동 경로를 알 수 있으므로, 이를 통해 그래프를 그릴 수 있다.

 

 

4. 다익스트라 알고리즘에서 반복자를 사용하는 이유

(1) 최단 거리 계산

출발 정점에서부터 지금까지의 최단 거리를 가지고 있는 정점들까지 순차적으로 방문할 수 있음

이후에 다음 방문할 정점을 선택하고 다른 정점으로 가는 경로의 최단 거리를 업데이트할 수 있음

 

(2) 우선순위 구현

방문하지 않은 노드 중에서 최단 거리를 가지는 노드를 선택

최단 거리가 작은 노드를 빠르게 찾을 수 있음

 

(3) 정점 방문 확인

중복된 정점을 다시 방문하지 않을 수 있음