다익스트라 구현

다익스트라 알고리즘은 해당 블로그에서 잘 설명되었기에 참고하시기 바랍니다.

https://alswnsdl.tistory.com/12

다익스트라 알고리즘(Dijkstra's algorithm) 개념

 

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

using namespace std;

struct Node {
	int n;
	int price;
};

vector<vector<Node>> alist(5);

void init() {
	alist[0].push_back({ 1,25 });
	alist[0].push_back({ 2,50 });
	alist[0].push_back({ 3,10 });
	alist[1].push_back({ 2,3 });
	alist[2].push_back({ 4,1 });
	alist[3].push_back({ 4,18 });
	alist[3].push_back({ 1,5 });
}

int result[5] = {0,999,999,999,999};
int used[5];

priority_queue<Node> q;

bool operator<(Node v, Node tar) {
	return tar.price < v.price;
}

int main() {
	init();
	q.push({ 0,0 });
	while (!q.empty()) {
		Node via = q.top();
		q.pop();
		if (used[via.n] == 1) continue;
		used[via.n] = 1;

		// 경유지 선택 되었으니까
		// 경유지에서 갈 수 있는 곳 다 for 탐색
		// result vs 경유지 거쳐가는거랑 비교해서
		// result 배열 갱신
		for (int i = 0; i < alist[via.n].size(); i++) {
			Node tar = alist[via.n][i];
			if (result[tar.n] > tar.price + via.price) {
				result[tar.n] = tar.price + via.price;
				q.push({ tar.n, result[tar.n] });
			}
		}
	}
	for (int i = 0; i < 5; i++) cout << result[i] << endl;
	return 0;
}