다익스트라 알고리즘

첫 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

int ch[30], dist[30];

struct Edge{
	int node, cost;
	Edge(int a, int b){
		node = a;
		cost = b;
	}
	bool operator<(const Edge &b) const{
		return cost > b.cost;
	}
	
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	vector<Edge> map[30];
	
	int n,m,a,b,c,i;
	
	for(i=2; i<30; i++){
		dist[i] = INT_MAX;
	}
	
	
	scanf("%d %d",&n,&m);
	
	for(i=0; i<m; i++){
		scanf("%d %d %d",&a,&b,&c);
		map[a].push_back(Edge(b,c));
	}
	
	
	
	priority_queue<Edge> Q;
	//Edge(노드, 1에서부터 거리)
	 
	Q.push(Edge(1,0));
	
	
	while(!Q.empty()){
		auto cur = Q.top();
		Q.pop();
		
		if(cur.cost==INT_MAX) break;
		if(ch[cur.node]==0){
			ch[cur.node] = 1;
			dist[cur.node] = cur.cost;
			
			for(i=0; i<map[cur.node].size(); i++){
				Q.push(Edge(map[cur.node][i].node, cur.cost + map[cur.node][i].cost));				
			}
		}
		
	}
	
	
	for(i=2; i<=n; i++){
		if(dist[i]==INT_MAX){
			printf("%d : impossible\n", i);
		}
		else printf("%d : %d\n", i, dist[i]);
	}
	
}

우선순위 큐에서 빠져나오면 해당 정점의 dist값이 최소인게 분명해서

 

해당 정점을 check 해주고 다시 방문하지 않게 해주었다.

 

해설 코드에서는 정점이 check여부를 사용하지 않고,

 

해당정점의 cost값이 현재 dist 배열에 있는 값보다 크다면 continue 해서

 

그 정점에서 다른 정점으로 이동하지 않게 처리했다.

 

 

 

 

해설 코드

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

struct Edge{
	int vex, dis;
	Edge(int a, int b){
		vex = a;
		dis = b;
	}
	bool operator<(const Edge &b)const{
		return dis>b.dis;	
	}
	
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, n, m, a, b, c;
	scanf("%d %d",&n,&m);
	
	vector<pair<int, int > > graph[30];
	vector<int> dist(n+1, INT_MAX);
	priority_queue<Edge> Q;
	
	for(i=1; i<=m; i++){
		scanf("%d %d %d",&a,&b,&c);
		graph[a].push_back(make_pair(b,c));
	}
	
	Q.push(Edge(1,0));
	
	dist[1]=0;
	while(!Q.empty()){
		int now = Q.top().vex;
		int cost = Q.top().dis;
		Q.pop();
		
		if(cost > dist[now]) continue;
		
		for(i=0; i<graph[now].size();i++){
			int next = graph[now][i].first;
			int nextDis = cost+graph[now][i].second;
			
			if(dist[next]>nextDis){
				dist[next] = nextDis;
				Q.push(Edge(next, nextDis));
			}
				
		}

	}
	
	
	for(i=2; i<=n; i++){
		if(dist[i]==INT_MAX){
			printf("%d : impossible\n", i);
		}
		else printf("%d : %d\n", i, dist[i]);
	}
	
}