graph/dijkstra.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Laufzeit: O((|E|+|V|)*log |V|) 
void dijkstra(int start) {
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	vector<int> dist(NUM_VERTICES, INF), parent(NUM_VERTICES, -1);

	dist[start] = 0;
	pq.push(ii(0, start));

	while (!pq.empty()) {
		ii front = pq.top(); pq.pop();
		int curNode = front.second, curDist = front.first;
		
		if (curDist > dist[curNode]) continue;
		
		for (auto n : adjlist[curNode]) {
			int nextNode = n.first, nextDist = curDist + n.second;
			if (nextDist < dist[nextNode]) {
				dist[nextNode] = nextDist; parent[nextNode] = curNode;
				pq.push(ii(nextDist, nextNode));
			}
		}
	}
}