다익스트라 알고리즘

다익스트라 알고리즘이란?

 

 방향성을 갖거나 갖지않는 그래프에서 하나의 시작지점으로부터 다른 모든 정점까지의 최단 거리를 구해주는 알고리즘이다. 시작점을 아무곳으로 지정하여도 상관없다.

 플로이드 알고리즘과의 차이점은 플로이드 알고리즘의 경우에는 간선의 가중치 값에 음수가 존재한다면, 문제가 발생할 수 있으며 다익스트라 알고리즘을 사용할때, 간선의 가중치 값에 음수가 존재한다면 사용할 수 없다는 차이점이 존재한다.

또한, 길찾기 알고리즘의 대표적인 예시의 A* 알고리즘은 길찾기에 필요한 최단거리를 정확하게 계산하는것이 아닌 근사값을 추정한다는 점에서 차이점이 존재한다.

 

 

아래와 같은 그래프의 모양을 띄웠을때, 다익스트라 알고리즘을 한눈으로 살펴볼 수 있다.

 

<다익스트라 그래프>

 

 

해당 다익스트라 알고리즘을 직접 구현해보자!

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

// {비용, 간선 번호}
vector<pair<int, int>> adj[20005];
const int INF = 0x3f3f3f;
bool fix[20005];
int d[20005];
int V = 10;

void dijkstra_naive(int st)
{
	fill(d, d + V + 1, INF); // 최단 거리 테이블 INF 초기화.
	d[st] = 0;

	while (0)
	{
		int idx = -1;
		for (int i = 1; i <= V; i++)
		{
			if (fix[i]) continue;
			if (idx == -1) idx = i;
			else if (d[i] < d[idx]) idx = i;
		}

		if (idx == -1 || d[idx] == INF) // 모든 정점 탐색 완료.		
			break;
		fix[idx] = 1; // 정점 idx
		for (auto nxt : adj[idx])
			d[nxt.second] = min(d[nxt.second], d[idx] + nxt.first);
	}
}

 

구현 설명

우선 순위 큐를 이용한 다익스트라 알고리즘

1, 우선순위 큐(0, 시작점) 초기화

2. 우선순위 큐에서 가장 거리가 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 3번과정을 수행하지 않음

3. 원소가 가리키는 정점을 v라고 할때, v와 이웃한 정점들에 대해 최단거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가지면, 최단 거리값을 갱신하고 우선순위 큐에(거리, 이웃정점의 번호) 추가

4. 우선순위 큐가 빌때까지 2, 3번 과정을 반복

 

---

 

 

다익스트라 알고리즘 대표 예시.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int v, e, st;	// 정점, 간선, 시작점.

// {비용, 정점 번호}
vector<pair<int, int>> adj[20005];
const int INF = 1e9+10;

int d[20005]; // 최단거리 테이블.

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> v >> e >> st;
	fill(d, d + v + 1, INF);

	while (e--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back( {w,v});

	}

	priority_queue<pair<int, int>,
		vector<pair<int, int>>,
		greater<pair<int, int>>> pq;

	d[st] = 0;

	// 우선순위 큐에 (0, 시작점)
	pq.push({ d[st], st });
	while (!pq.empty())
	{
		auto cur = pq.top(); pq.pop();
		if (d[cur.second] != cur.first) continue;
		
		for (auto nxt : adj[cur.second])
		{
			if (d[nxt.second] <= d[cur.second] + nxt.first)continue;
			d[nxt.second] = d[cur.second] + nxt.first;
			pq.push({ d[nxt.second], nxt.second });

		}
	
	}

	for (int i = 1; i <= v; i++)
	{
		if (d[i] == INF) cout << "INF\n";
		else cout << d[i] << "\n";
	}

}