[PS] Dijkstra

Dijkstra 개념 및 방법

Dijkstra : 최단거리를 구하는 알고리즘
조건 : 가중치로 음수가 존재하는 그래프는 최단거리를 구할 수 없다.

방법

1. 아직 확정이 안된 점들 중에서 가장 거리가 짧은 점을 확정 짓는다.
2. 확장시킨 점에서부터 갈 수 있는 거리를 갱신시킨다.

Dijkstra 코드

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

struct Edge
{
	int to;
	int dist;
};

int operator<(Edge left, Edge right)
{	
	// dist 우선순위 : 작은순
	if (left.dist < right.dist) return 0;
	if (left.dist > right.dist) return 1;
	// to 우선순위 : 작은순
	if (left.to < right.to) return 0;
	if (left.to > right.to) return 1;

	return 0;
}

int n, e;
vector<vector<Edge>> v;
vector<int> dist(n + 1);

void input()
{	
	// 연결지점 마지막 번호와 도로 개수 입력받기!
	cin >> n >> e;
	v = vector<vector<Edge>>(e, vector<Edge>());
	// 출발,도착,거리 입력받기!
	for (int i = 0; i < e; i++)
	{
		int from, to, dist;
		cin >> from >> to >> dist;
		v[from].push_back({ to,dist });
	}
}

void dijkstra()
{
	dist = vector<int>(n + 1, 99999);
	vector<int> used(n + 1, 0);

	priority_queue<Edge> pq;

	// 시작점 셋팅
	dist[0] = 0;
	pq.push({ 0,0 });

	while (!pq.empty())
	{
		Edge now = pq.top();
		pq.pop();

		int minNode = now.to;
		int nowDist = now.dist;
		if (used[minNode] == 1) continue;
		used[minNode] = 1;

		// 현재 위치에서 갈 수 있는 곳 pq에 넣기
		for (int i = 0; i < v[minNode].size(); i++)
		{
			Edge edge = v[minNode][i];
			int to = edge.to;
			int d = edge.dist;
			if (dist[to] <= dist[minNode] + d) continue;
			dist[to] = dist[minNode] + d;
			// 중첩된 거리를 계산 후 pq에 push
			pq.push({ to,dist[to] });
		}
	}
}

int main() 
{
	input();
	dijkstra();
	cout << dist[n] << endl;

	return 0;
}