다익스트라 최단경로 알고리즘

다익스트라 알고리즘은 도로 교통망 같은 곳에 나타날 수 있는 그래프에서 꼭짓점 간의 최단경로를찾는 알고리즘이다

도시의 지도에서 출발지와 목적지 사이의 가장 짧은 거리를 찾는다고 가정하면 다익스트라 알고리즘에서는 교차점마다 출발지로부터의 거리를 적어서 가장짧은거리를 찾는다

다익스트라 알고리즘에서는 우선 모든 교차점에 무한대를 적어놓는다. 여기서 무한대는 실제거리가 무한대가 아니라 직접 교차로로 가보지 않아 그 거리를 알수 없기 때문에 무한대로 표현을 하는것이다

다음으로 모든 교차점을 표시할때 까지 반복을 한다 . 우선 현재 위치를 정하고 시작점으로 부터의 거리를 쓴다 시작할때의 현재위치는 시작점이며 이때의 거리는 0이다

그 다음 현재 위치와 연결되어있는 교차로들의 거리를 갱신을 시작한다
현재 위치에는 시작점으로 부터 가장 짧은 거리가 쓰여져 있을것이다
현재 위치 T에 쓰여 있는거리를 A 이웃 교차로로 연결된 도로의길이를 B
이웃교차로에 쓰여있는거리를 C라고 할때 A+B<C이면 이웃교차로에 최단거리는 A+B이며 이값은 T로부터 계산되었다라고 쓰며 , 이 과정을 완화라고 한다

이 알고리즘은 목적지를 향해 조사하는것이아닌 목적지까지의 최단거리보다 짧은교차로들을 모두 고려하기때문에 최단거리를 찾을 수있게되는것이다.

개념자체는 이렇지만 , 코드를 먼저보고 개념을 다시보니 이해가 쉬웠던거같다.

다익스트라 코드

이번에는 백준 1753번의 '최단경로'라는 문제를 다익스트라 알고리즘을 이용하여 문제를 풀어보았다

#include<bits/stdc++.h>
using namespace std;
#define SIZE 200001
#define INF 999999
int v, e, s, a, b, c;
int Dist[SIZE];
struct Node
{
	int x, Distance;
	
};
vector<Node>vec[SIZE];
void Reset()
{
	for (int i = 1; i <= v; i++)
	{
		Dist[i] = INF;
		vec[i].clear();
	}
}
void Dystra(int start)
{
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>que;
	Dist[start] = 0;
	que.push({0,start });
	while (!que.empty())
	{
		int Dis = que.top().first;
		int x = que.top().second;
		que.pop();
		if (Dis > Dist[x])continue;
		for (auto next : vec[x])
		{
			int temp_x = next.x;
			int temp_dis = next.Distance;
			if (Dist[temp_x] > Dis + temp_dis)
			{
				Dist[temp_x] = Dis + temp_dis;
				que.push({Dist[temp_x],temp_x});
			}
		}
	}
}
void Insert()
{
	cin >> v >> e;
	Reset();
	cin >> s;
	for (int i = 1; i <= e; i++)
	{
		cin >> a >> b >> c;
		vec[a].push_back({ b,c });
		
	}
	Dystra(s);
	for (int i = 1; i <= v; i++)
	{
		if (Dist[i] == INF)
		{
			cout << "INF" << '\n';
			continue;
		}
		cout << Dist[i] << '\n';
	}
}
int main()
{
	Insert();
	return 0;
}

우선순위 큐 사용

우선순위 큐 (Priority Queue)
우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

우선순위 큐를 사용한 이유

일반적인 다익스트라는 시간복잡도로 O(v^2)의 시간 복잡도를 가진다 이때의 V는 노드의 개수이다
모든 노드들을 탐색하여 최단거리가 가장 짧은 노드를 찾아야하기에 이러한 시간복잡도가 걸리게된다
우선순위큐를 사용하여 다익스트라 알고리즘을 만들경우 시간복잡도가
O(ElogV)의 시간이 걸리게된는데 이때 v는 노드개수 E는 간선의 개수가 된다

무한대로 표현

void Reset()
{
	for (int i = 1; i <= v; i++)
	{
		Dist[i] = INF;
		vec[i].clear();
	}
}

현재 Reset함수를 통해 모든 경로들을 INF,즉 무한대로 표현을 해주었다.
아직 어느 정점에서 시작하는지 , 경로가 어떻게 되는지 알수있는게 하나도 없기에 INF 처리를 해주었다

다익스트라

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>que;
Dist[start] = 0;
que.push({0,start });
while (!que.empty())
{
	int Dis = que.top().first;
	int x = que.top().second;
	que.pop();
	if (Dis > Dist[x])continue;
	for (auto next : vec[x])
	{
		int temp_x = next.x;
		int temp_dis = next.Distance;
		if (Dist[temp_x] > Dis + temp_dis)
		{
			Dist[temp_x] = Dis + temp_dis;
			que.push({Dist[temp_x],temp_x});
		}
	}
}

시작점 start가 주어져 Dist[start]=0으로 설정해준다(시작점은 이미 위치해있기 때문)

temp_x = 위에서 설명한 위치 T
Dist[temp_x] = 이웃교차로에 쓰여있는거리: C
Dis = 이웃교차로로 연결된 교차로 A
temp_dis = 이웃 교차로로 연결된 도로의길이를 B
A+B<C 는 Dis+temp_dis<Dist[temp_x]로 표현을 해주었다