다익스트라 Dijkstra C++

개요

특징

1. 특정 노드에서 연결 되어 있는 모든 노드까지의 최단 거리를 구할 수 있다.
2. 가중치는 양수여야만 하며 음수일 경우 해당 간선을 계속 방문하게 되어 루프에 빠지게 된다.
3. 양방향 및 단방향 그래프 및 2차 배열 형태에서도 에 모두 사용 가능하다.

동작 요약

1. 모든 노드 까지의 거리를 2e9 혹은 INT_MAX와 같은 값을 사용하여 최대치로 설정한다.
2. 시작점 노드 자기 자신 까지의 거리를 0으로 설정하고, 우선순위 큐에 자신을 추가한다.
3. 첫 탐색 시 자신과 연결된 인접 리스트를 참고하여 해당 노드까지의 거리가 현재 거리보다 짧다면 갱신해 주고 해당 노드를 우선순위 큐에 넣어준다.
4. 이후 우선순위 큐에 있는 노드와 연결된 인접 리스트를 참고하여 거리 정보가 최소가 되도록 갱신해 주는 작업을 반복한다.
5. 우선순위 큐에 더 이상 간선 정보가 없을 때 까지 진행하고 원하는 노드까지의 거리를 인덱싱을 통해 출력한다.

 

예제

그래프 정보

위와 같은 그래프가 존재할때 시작점 0번 노드에서 부터 각 노드까지의 최단거리를 구해보자

 

코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

struct Edge {
	int num;
	int cost;
	bool operator<(Edge right)const {
		return cost > right.cost;
	}
};

vector<Edge>alis[20];
int N, M;

int dist[20];
int visited[20];
void dijkstra(int start) {
	//1. PQ준비
	priority_queue<Edge>pq;
	//2. 시작 노드 삽입
	pq.push({ start, 0 });
	//3. 정답 배열 초기화
	for (int i = 0; i < N; i++) {
		dist[i] = 2e9;
	}
	//4. 시작노드의 정답을 기록 하고 진행
	dist[start] = 0;

	// 구현 단계
	while (!pq.empty()) {
		// 1. PQ 에 top 에 있는 노드를 확인하고 추출(now 위치에 있다)
		Edge now = pq.top(); pq.pop();
		if (dist[now.num] < now.cost) continue; // now.cost now까지의 누적 가중치

		// 2. now 에서 갈수 있는 next 후보 찾기
		for (int i = 0; i < alis[now.num].size(); i++) {
			Edge next = alis[now.num][i]; //next 후보 확인
			int nextcost = dist[now.num] + next.cost;
			// 3. 판별식
			if (dist[next.num] <= nextcost) continue;                    
			dist[next.num] = nextcost;
			pq.push({ next.num, nextcost }); //PQ에 등록
		}
	}
	for (int i = 1; i < N; i++) {
		cout << "노드 " << i << "까지의 거리 : " << dist[i] << "\n";
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		alis[from].push_back({ to,cost });
		alis[to].push_back({ from,cost });
	}
	dijkstra(0);
}

 

입력

9 12
0 1 7 
0 2 12
1 4 9
1 3 42
2 3 31
2 7 27
3 4 27
3 6 8
7 6 16
4 5 42
5 6 20
6 8 3

 

출력

노드 1까지의 거리 : 7
노드 2까지의 거리 : 12
노드 3까지의 거리 : 43
노드 4까지의 거리 : 16
노드 5까지의 거리 : 58
노드 6까지의 거리 : 51
노드 7까지의 거리 : 39
노드 8까지의 거리 : 54