다익스트라

시작점이 정해진 상태이고 가중치>=0일 때 최단경로 구할 때 사용. 사이클이 있어도 사용가능.

하나의 정점을 검사할 때마다 모든 간선에 대해 검사하고, 최소힙(우선순위 큐)에 들어가는 것은 최악의 경우 간선 개수만큼 들어가므로 O(ElogE)

 

bst(set)을 사용해서 유효한 {dist, i}만을 유지한다면 O(ElogV)지만 속도가 크게 차이 안날 뿐더러, 우선순위 큐의 시간복잡도 상수가 더 작다. 구현이 편한 ElogE코드를 사용하자

 

 

 

필요한 것 :

   bool vst[MAX] {0}

   int d[MAX] {INF}

   vector<int> g[MAX]

   priority queue (dist 가장 가까운 것부터)

int  main() {
	bool vst[MAX] = {0};
	vector<P> g[MAX]; //{도착지,가중치}
	int d[MAX];
	fill(d, d + MAX, INF); //최소값이 갱신될 것이므로 INF로 초기화
    
	//시점, 종점
	int start, end; scanf("%d %d", &start, &end);
	start--; end--;

	//dist[v]에 대한 최소힙
	priority_queue<P, vector<P>, greater<P>> pq; //d[v], v
	d[start] = 0;
	pq.push({ d[start], start });
    
	while (!pq.empty()) {
		int u = pq.top().second; pq.pop();
		if (vst[u]) continue;
        
		vst[u] = true;
        
        //연결된 모든 부분 검사
		for (auto& p : adj[curr]) {
			int v = p.first, w = p.second;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				pq.push({ d[v], v });
			}
		}
	}
	printf("%d\n", d[end]);
}

 

 

기본문제:

https://www.acmicpc.net/problem/1753