[알고리즘] 최단 경로(다익스트라), MST (프림)

포인트

1. 다익스트라 알고리즘과 프림 알고리즘은 거의 차이가 없다. 

다익스트라는 값을 계속해서 더해서 나간다고 생각을 하면 된다.

다익스트라

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


using namespace std;

vector<pair<int, int>> map[101];

vector<int> dijkstra(int start, int goal) {
	vector<int> dist (goal, 9876554321);
	dist[start]=0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push ({ 0, start });

	while(!pq.empty()) {
		int x, cost;
		tie (cost, x)=pq.top ();
		pq.pop ();

		if (dist[x] < cost) continue;

		for(auto ele : map[x]) {
			int ncost=cost + ele.first;
			if (ncost < dist[ele.second]) {
				dist[ele.second]=ncost;
				pq.push ({ ele.first, ncost });
			}
		}
	}	
}

int main() {
	int n, m;

	cin >> n >> m;

	for(int i=0; i<m; i++) {
		int start, goal, cost;

		map[start].push_back ({ goal, cost });
		map[goal].push_back ({ start, cost });
	}

	vector<int> dists=dijkstra (0, n); //0에서 부터 목적지까지


	for (auto ele : dists) cout << ele << ' ';
	cout << '\n';
	
	return 0;
	
}

프림

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

using namespace std;
int n, m;
bool visited[1001];
vector<pair<int, int>> map[1001]; //가중치, 목적지
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //가중치기준 최소힙

int prim() {
	int ans = 0;
	pq.push({0, 1});
	while (!pq.empty()) {
		pair<int, int> cur = pq.top();
		pq.pop();
		if (visited[cur.second]) continue; //방문했으면 거른다.
		visited[cur.second] = true;
		ans += cur.first;
		for (auto next : map[cur.second]) {
			if (!visited[next.second]) {
				pq.push(next);
			}
		}
	}
	return ans;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		map[a].push_back({c, b});
		map[b].push_back({c, a});
	}
	int result = prim();
	cout << result << endl;

	return 0;
}

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다.