[알고리즘] 다익스트라 (Dijkstra)

그래프 알고리즘 중 최소비용을 구하는 데는 다익스트라 알고리즘, 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다.

 

그중 다익스트라 알고리즘은 시작 정점부터 다른 정점까지의 최단 경로를 구하기 위한 그래프 알고리즘이다.

이러한 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지의 최단 경로를 방문하여 각 정점까지의 최단 경로를 모두 찾는다.

즉, 매번 최단 경로의 정점을 선택하여 탐색을 반복하는 것이다.

다익스트라 알고리즘은 노드의 재방문을 허용하지 않기 때문에 어느 간선의 가중치라도 음수가 있으면 안된다는 특징이 있다.

(음수 간선이 존재할 때는 벨만-포드 알고리즘, SPFA 알고리즘을 이용하여 최소비용을 구할 수 있다.)

 

 

다익스트라에서 노드 간의 연결은 weight (가중치)값으로 판단한다.

특정 값이 있다면 노드 사이가 연결되어 있다는 뜻이고, 무한값(INF)라면 연결되어있지 않다는 뜻이다.

 

2차원 배열인 weight 로 노드 간의 비용(가중치)을 나타내고, visit 배열로 방문한 노드를 bool 변수로 체크한다. 

dist 배열은 시작점부터 각 노드까지의 비용을 담은 1차원 배열이다.

 

📄 다익스트라

#include <iostream>
#define INF 1000000000
#define N 5

using namespace std;

int weight[N][N] =
{
	{0,	7,	4,	6,	1},
	{INF,0,	INF,INF,INF},
	{INF,2,	0,	5,	INF},
	{INF,3,	INF,0,	INF},
	{INF,INF,INF,1,	0}
};

bool visit[N];
int dist[N];
int minNode;

int GetMinimumNode()
{
	int min = INF;
	int minpos = 0;
	for (int i = 0; i < N; i++)
	{
		// 방문하지 않았고, 비용이 가장 작은 노드 탐색
		if (dist[i] < min && !visit[i])
		{
			min = dist[i];
			minpos = i;
		}
	}
	return minpos;
}

void dijkstra(int start)
{
	for (int i = 0; i < N; i++)
		dist[i] = weight[start][i];

	visit[start] = true;
	for (int i = 0; i < N - 1; i++)
	{
		minNode = GetMinimumNode();
		visit[minNode] = true;

		for (int j = 0; j < N; j++)
		{
			// 방문하지 않은 노드 중에, 경유하는 노드 경로가 기존 경로보다 더 가까워지면 갱신
			if (!visit[j] && (dist[minNode] + weight[minNode][j] < dist[j]))
				dist[j] = dist[minNode] + weight[minNode][j];
		}
	}
}

int main()
{
	dijkstra(0);

	for (int i = 0; i < N; i++)
		cout << dist[i] << " ";
	cout << endl;

	return 0;
}

 

이러한 다익스트라의 시간복잡도는 for문을 N-1번 반복하고, 각각의 최소비용노드를 찾을 때 N번을 또 비교하기 때문에 O(N^2)이다. 여기서 N은 노드의 개수를 의미한다.

즉, 이러한 소스코드는 노드의 수가 많아질수록 비효율적이기 때문에 우선순위 큐로 구현하는 방법이 있다.

 

우선순위 큐를 이용하여 다익스트라 알고리즘을 구현하면, 방문노드를 체크하는 visit 배열과, GetMinimumNode 함수가 필요 없다.

 

 

📄 다익스트라 (우선순위큐)

#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000000
#define N 3

using namespace std;

vector<pair<int, int>> nodes[N];
int dist[N];

void dijkstra(int start)
{
	priority_queue<pair<int, int>> pq;

	pq.push({ 0, start });
	dist[start] = 0;

	while (!pq.empty())
	{
		int cost = -pq.top().first; // 우선순위큐가 내림차순이므로 -처리
		int here = pq.top().second;
		pq.pop();

		// 이미 최단거리 정보라면 넘어가기
		if (dist[here] < cost) continue;

		for (int i = 0; i < nodes[here].size(); i++)
		{
			int via_cost = cost + nodes[here][i].first;

			// here을 경유하는 경로가 더 빠르다면 갱신
			if (via_cost < dist[nodes[here][i].second])
			{
				dist[nodes[here][i].second] = via_cost;
				pq.push({ -via_cost, nodes[here][i].second });
			}
		}
	}
}

int main()
{
	for (int i = 0; i < N; i++)
		dist[i] = INF;

	nodes[0].push_back({ 5,1 });
	nodes[0].push_back({ 1,2 });
	nodes[2].push_back({ 3,1 });

	dijkstra(0);

	for (int i = 0; i < N; i++)
		cout << dist[i] << endl;

	return 0;
}

---

참조

https://charles098.tistory.com/11

[C++] 다익스트라(Dijkstra)