22.07.24

80. 다익스트라 알고리즘

1. 다익스트라 알고리즘
   1-1. 개요
   다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

참고로 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다.

(출처: https://velog.io/@717lumos/알고리즘-다익스트라Dijkstra-알고리즘)

이해하는데 시간이 걸렸고, 아직까지도 명확하게 잡히지 않는다. 내가 이해하고 있는게 정확히 맞는지도 잘 모르겠다.
그래도 현재 이해하고 있는대로 적어보자면,
결국 최소 비용으로 어느 지점에 도달하기 위해서는 현재 상태에서 선택할 수 있는 방향중 가장 최소 비용인 길을 선택하는 것이 효율적이다.

따라서 priority_queue 를 이용해 현재 노드에서 갈 수 있는 노드들중 최소 비용인 곳을 선택하고
현재노드까지 비용 + 다음 노드로 가는 비용 vs 이미 파악된 다음 노드로 가는 비용을 비교해서 더 작은 값으로 최신화 한다.

결국 계속 최소비용을 비교해가면서 탐색을 진행하는 개념이고, 그 과정에서 priority_queue가 이용되는데, 솔직히 처음에 그냥 queue로 풀었을 때도 답이 나와서 명확히 무슨 차이인지 잘 이해가 안간다...

int main(){
	
	freopen("input.txt","rt",stdin);

	int n, m, a, b, c;
	cin>>n>>m;

	vector<int> dst(21,2147000000);
	vector<vector<Data>> city(21);
	priority_queue<Data> pQ;
	
	
	for(int i=0; i<m; i++){
		cin>>a>>b>>c;
		city[a].push_back(Data(b,c));
	}
	
	pQ.push(Data(1,0));
	dst[1] = 0;
	while(!pQ.empty()){
		int x = pQ.top().n;
		pQ.pop();
		for(int i=0; i<city[x].size(); i++){
			int ct = dst[x] + city[x][i].cost; 
			if(ct< dst[city[x][i].n]){
				dst[city[x][i].n] = ct;
				pQ.push(city[x][i]);
			}
		}	
	}
	

	for(int i=2; i<=n; i++){
		cout<<i<<" : ";
		if(dst[i]==2147000000)
			cout<<"impossible"<<endl;
		else
			cout<<dst[i]<<endl;
	}
	
	return 0;

}

다음에 다시 한 번 보고 이해해보기로