최단 거리(1) 다익스트라 알고리즈

최단 거리(1) 다익스트라 알고리즘

최단거리 알고리즘에는 다익스트라, 플로이드, 벨만포드 세가지 방법이 있습니다. 

 

다익스트라와 벨만포드는 한 시작점에서 다른 정점까지의 최단거리를 구하는 것이고 플로이드는 모든 정점에서 모든 정점까지의 최단 거리를 구하는 것입니다. 

 

오늘은 3가지 중 다익스트라에 대해 정리해보겠습니다. 

 

1. 다익스트라는 시작 정점에서 다른 정점까지의 거리를 모두 무한대로 세팅한 후 시작합니다.

s 정점까지의 가중치와 연결된 정점까지의 가중치 값을 더해서 연결된 정점까지의 가중치 보다 작다면 값을 바꿔줍니다. 

 

2. 이전 라운드를 제외한 다른 정점들 사이에서 최단 거리를 구해줍니다. 

 

새로운 정점 s를 뽑는 방법은 가장 작은 가중치를 갖는 정점을 뽑습니다. 정점 s를 시작으로 다른 연결된 정점들의 가중치를 update해줍니다. 

 

3. 가장 낮은 가중치 7을 기준으로 다른 정점의 가중치를 update

 

이전 과정과 같이 계속 반복해주며 최단 거리를 구해줍니다. 

 

 

주의할 점 

다익스트라의 경우 음수 가중치가 존재하면 안됩니다. 

음수 가중치가 안되는 이유는 최소 가중치의 정점을 뽑는 이유는 해당 정점의 가중치가 더 이상 업데이트가 안되기 때문입니다.

만약 음수 가중치가 있다면 이미 방문했던 노드들보다 새롭게 방문해야 하는 노드들의 가중치가 더 작아야합니다. 하지만 음수 가중치 때문에 이미 방문했던 노드들의 가중치가 더 작이질 수 있기 때문입니다. 

 

Relax 함수

 

모든 최단 거리 알고리즘에서 유용하게 사용되는 함수이다. 이 함수는 다른 정점을 거쳐서 가는게 더 빠른가를 비교하는 함수이다. 

 

d(v) = min(d(v), d(u) + d(v))

 

시간 복잡도 

 

새로운 시작 정점을 뽑을 때의 기준은 최소 가중치의 정점을 뽑는 것인데 이 방법에 따라서 시간 복잡도가 달라지게 됩니다. 

 

우선순위 큐를 사용하지 않고 최소 정점을 뽑을 때 O(n^2)

우선순위 큐를 사용하며 최소 정점을 뽑을 때 O(nlog2n + mlog2n)

 

각 정점 별로 한번 씩 연산 n

최소 값을 뽑을 때 최소 힙으로 log2n이 들어서 -> nlog2n

 

이후 각 정점별 길 반복문 m

Relax 함수 새로운 값을 우선순위 큐에 넣어야 함으로 log2n -> mlog2n

 

 

 

백준 문제

https://www.acmicpc.net/problem/1753

1753번: 최단경로

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

int V, E;
int startPoint;
int INF = 987654321;
int visited[20002];
int vertex[20002];
vector <pair<int, int> > pathSaver[20002];
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

void input();
void dajickStra();

int main(){
	input();
	dajickStra();
	for(int i = 1; i <= V; i++){
		if(vertex[i] == INF)
			printf("INF\n");
		else
			printf("%d\n", vertex[i]);
	}
}

void input(){
	int u, v, w;
	scanf("%d %d", &V, &E);
	scanf("%d", &startPoint);

	for(int i = 1; i <= E; i++){
		scanf("%d %d %d", &u, &v, &w);
		pathSaver[u].push_back(make_pair(w, v));
		
	}

	for(int i = 1; i <= V; i++)
		vertex[i] = INF;

	pq.push(make_pair(0, startPoint));
	vertex[startPoint] = 0;
}


void dajickStra(){

	while(!pq.empty()){
		pair<int, int> now = pq.top();
		int nowWeight = now.first;
		int nowPoint = now.second;
		pq.pop();
		visited[nowPoint] = 1;
		for(int i = 0; i < pathSaver[nowPoint].size(); i++){
			pair<int, int> next = pathSaver[nowPoint][i];
			int nextWeight = next.first;
			int nextPoint = next.second;
			if(!visited[nextPoint]){
				if(vertex[nextPoint] > nowWeight + nextWeight){
					vertex[nextPoint] = nowWeight + nextWeight;
					pq.push(make_pair(vertex[nextPoint], nextPoint));
				}
			}
		}
	}
}