[C++] 다익스트라 알고리즘 ⭐

다익스트라(Dijkstra) 알고리즘은 그래프 내에서 특정 출발 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘 중 하나입니다. 다익스트라 알고리즘은 가중치가 양수인 간선을 가지는 그래프에서 사용됩니다.

 

우선순위 큐를 사용하여 효율적으로 접근합니다. 그 이유는, Dijkstra 알고리즘에서 최소 가중치를 가진 간선을 선택하는 데 필요한 노드의 후보 집합을 효율적으로 관리하기 위함입니다.

최소 가중치 간선 선택
Dijkstra 알고리즘은 시작 노드에서부터 다른 노드로 가는 최단 경로를 찾는 것이 목적입니다. 이를 위해 각 단계에서 최소 가중치를 가진 간선을 선택해야 합니다. 우선순위 큐는 간선을 가중치 순으로 관리하므로 최소 가중치 간선을 빠르게 선택할 수 있습니다.

노드의 후보 집합 관리
Dijkstra 알고리즘은 노드의 후보 집합을 관리해야 합니다. 이 집합은 아직 최단 경로가 결정되지 않은 노드들로 구성됩니다. 우선순위 큐를 사용하면 후보 집합에서 가장 가까운 노드를 효율적으로 선택하고, 각 노드까지의 현재 최단 경로를 유지할 수 있습니다.

효율성
우선순위 큐를 사용하면 간선 선택 및 노드 후보 집합 관리가 효율적으로 이루어집니다. 간선을 선택하는 데 O(log(N)) 시간이 소요되고, 후보 집합에서 노드를 선택하거나 갱신하는 데 O(log(N)) 시간이 걸립니다. 이러한 효율성으로 Dijkstra 알고리즘은 빠른 실행 속도를 보이며, 최단 경로를 효과적으로 찾을 수 있습니다.

 

📄문제

아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로그램을 작성하세요. 

(경로가 없으면 Impossible를 출력한다)

 

⬇️ 입력

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다.

6 9 1 2 12 1 3 4 2 1 2 2 3 5 2 5 5 3 4 5 4 2 2 4 5 5 6 4 5

 

⬆️ 출력

1번 정점에서 각 정점으로 가는 최소 비용을 2번 정점부터 차례대로 출력하세요.

2 : 11 3 : 4 4 : 9 5 : 14 6 : impossible

 

📝 풀이

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

struct Edge
{
	int to;
	int weight;

	Edge(int to, int weight) : to(to), weight(weight) {}

	bool operator < (const Edge& ref) const
	{
		return weight > ref.weight;
	}
};

int main()
{
	priority_queue<Edge> q;
	vector<pair<int, int>> graph[21];
	vector<int> dist(21, INT_MAX);

	int N, M, f, t, w;
	scanf_s("%d %d", &N, &M);

	for (int i = 0; i < M; ++i)
	{
		scanf_s("%d %d %d", &f, &t, &w);
		graph[f].push_back({ t, w });
	}

	// 1번 간선에서 시작
	q.push(Edge(1, 0));
	dist[1] = 0;

	while (!q.empty())
	{
		int current = q.top().to;
		int weight = q.top().weight;
		q.pop();

		// 해당 정점으로 갈 때, 이미 더 적은 비용의 거리가 있다면 리턴
		if (weight > dist[current])
			continue;

		// current 정점으로부터 뻗어나갈 수 있는 모든 방향으로 방문하기
		for (int i = 0; i < graph[current].size(); ++i)
		{
			// 다음 노드의 번호와 누적 가중치 가져오기
			int next = graph[current][i].first;
			int nextWeight = weight + graph[current][i].second;

			// 해당 노드까지의 비용이 저장된 비용보다 적다면?
			if (dist[next] > nextWeight)
			{
				// 비용 갱신
				dist[next] = nextWeight;

				// 해당 노드 방문
				q.push(Edge(next, nextWeight));
			}
		}
	}

	for (int i = 2; i <= N; ++i)
	{
		printf("%d : ", i);

		if (dist[i] == INT_MAX)
			printf("impossible");
		else
			printf("%d", dist[i]);

		printf("\n");
	}
}

• 인접리스트에 간선에 대한 정보를 저장합니다.
• 우선순위 큐를 이용하여 다음 노드를 방문할 때 더 효율적으로 탐색합니다.
• 각 간선에 누적된 가중치를 비교하여, 방문할 때 비용이 더욱 적다면, 비용을 갱신하면서 반복합니다.