다익스트라 c++

하나의 시작점으로부터 다른 정점들까지의 최단거리를 구하는 알고리즘

O(ElgE)

 

1753

순서

1. 거리 무한으로 해놓고

2. 정점들 연결해주고

3. 초기값 넣어주고

4. 거리값이 최소값인지 확인하고

5. 최단거리테이블 값과 현재 정점을 거쳐가는 값을 비교

 

int v, edges, start;
vector<pair<int, int>> adj[20005]; //거리, 정점
int d[20005];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a, b, c;
	cin >> v >> edges >> start;
	fill(d, d + v + 1, 12345678);
	for (int i = 0; i < edges; i++) {
		cin >> a >> b >> c;
		adj[a].push_back({ c,b }); //first : 거리, second : 정점
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	d[start] = 0;
	pq.push({ d[start], start }); //우선순위 큐에 (0, 시작점) 추가

	while (!pq.empty()) {
		auto cur = pq.top(); //우선순위큐에서 거리가 가장 작은 원소를 선택하고
		pq.pop();
		if (d[cur.second] != cur.first) continue; //거리가 최소값이 아닌경우
		for (auto repe : adj[cur.second]) { //현재 정점이 가리키는 정점들에 대해
			//최단거리 테이블 값에 있는게 cur을 거쳐가는것보다 더 작은 값이면 continue;
			if (d[repe.second] <= d[cur.second] + repe.first) continue; 
			//최단거리 테이블 값보다 cur을 거쳐가는게 더 작은 값이면
			d[repe.second] = d[cur.second] + repe.first; //거리 저장하고
			pq.push({ d[repe.second], repe.second }); //큐에넣기
		}
	}

	for (int i = 1; i <= v; i++) {
		if (d[i] == 12345678) cout << "INF\n";
		else cout << d[i] << '\n';
	}
}