다익스트라 알고리즘

방향성이 있는 그래프에서 우선순위큐를 사용하여 다익스트라 알고리즘을 구현하고 시작점에서부터 각 노드까지의 최단경로를 구하는 코드이다.

#include <iostream>
#include <queue>
#include <vector>

#define MAX 20001
#define INF 987654321
using namespace std;

int v, e, start;
int dijkstra[MAX];
vector<pair<int, int>> vertex[MAX];

void solution()
{
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	dijkstra[start] = 0;
	while (!pq.empty())
	{
    	//우선순위큐는 내림차순이므로 '-'를 붙여 작은 값이 더 우선순위에 오도록 함
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		for (int i = 0; i < vertex[cur].size(); i++)
		{
			int next = vertex[cur][i].first;
			int n_cost = vertex[cur][i].second;
			if (dijkstra[next] > cost + n_cost)
			{
				dijkstra[next] = cost + n_cost;
				pq.push({ -dijkstra[next], next });
			}
		}
	}

}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int a, b, c;
	cin >> v >> e >> start;
	
	for (int i = 0; i < e; i++)
	{
		cin >> a >> b >> c;
		vertex[a].push_back({b,c});
	}
	for (int i = 1; i <= v; i++)
		dijkstra[i] = INF;
	solution();
	for (int i = 1; i <= v; i++)
	{
		if (dijkstra[i] == INF)
			cout << "INF\n";
		else
			cout << dijkstra[i] << "\n";
	}

	return 0;
}

참고: https://yabmoons.tistory.com/364