[2022 1학기] 3주차 - 다익스트라

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

Dijkstra 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘

특정 노드에서 그래프의 모든 노드로 가는 최단 경로를 찾는 알고리즘

1:N관계이며 음수가중치는 없다

 

2. 동작 원리

dist배열은 시작 노드에서 i번째 노드까지의 거리를 뜻하고, 처음 시작점을 제외한 모든 노드를 INF로 초기화해줘야 함

방문하지 않은 정점 중에서 시작 노드로부터 거리가 가장 가까운 정점을 방문하고

방문한 정점에서 인접한 정점들에 대해서 거리를 갱신해줌

시간복잡도를 줄이기 위해 우선순위 큐를 이용

우선순위 큐는 내림차순으로 정렬되기 때문에 값을 넣을 때 -를 붙여주고 값을 빼낼 때도 -를 붙여서 빼준다 

 

3. 코드

int start;
int dist[20010];
vector<P> edge[20010];

void dijkstra() {
	priority_queue <P> 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 < edge[here].size(); i++) {
			int next = edge[here][i].first;
			int nextcost = edge[here][i].second;

			if (dist[next] > dist[here] + nextcost) {
				dist[next] = dist[here] + nextcost;
				pq.push({ -dist[next], next });
			}
		}

	}
}

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!