dijkstra

다익스트라 알고리즘

struct edge {
	int end, cost;
};

vector<vector<edge> > graph;
vector<int> costs;

void dijkstra(int start) {
	// cost, start vertex
	// 기존 priority_queue는 내림차순으로 정렬한다.
	// 인접한 노드들을 방문할 때 비용이 최소인 노드부터 방문하므로 우선순위 큐에 비용을 음수 처리
	priority_queue< pair<int, int> > pq;
	pq.push({ 0, start });

	// 노드의 거리 갱신은 V-1 번 만큼 하면 된다. 
	while (!pq.empty()) {
		int now_node = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		// 현재 노드에서 부터 주변에 있는 얘들의 값을 갱신한다. 
		for (edge current : graph[now_node]) {
			int new_val = costs[now_node] + current.cost;
			int before_val = costs[current.end];

			// 현재 노드로 부터 연결된 엣지의 목적지까지 가는 거리와 기존의 거리를 비교하여, 
			// 기존의 것이 더 크면 값을 갱신한다.  
			if (new_val < before_val) {
				int destination = current.end;

				costs[destination] = new_val;
				pq.push({ -new_val, destination });
			}
		}
	}
	return;
}

초기화

// initialize 
for (int i = 1; i <= V; i++) {
	costs[i] = INF;
}
costs[start] = 0;