Sobre

encontra menor distancia de x

para todos os vertices

se ao final do algoritmo d[i] = LINF,

entao x nao alcanca i

O(m log(n))

Link original: dijkstra.cpp

Código 

  ll d[MAX];
vector<pair<int, int>> g[MAX]; // {vizinho, peso}

int n;
 
void dijkstra(int v) {
	for (int i = 0; i < n; i++) d[i] = LINF;
	d[v] = 0;
	priority_queue<pair<ll, int>> pq;
	pq.emplace(0, v);
 
	while (pq.size()) {
		auto [ndist, u] = pq.top(); pq.pop();
		if (-ndist > d[u]) continue;
 
		for (auto [idx, w] : g[u]) if (d[idx] > d[u] + w) {
			d[idx] = d[u] + w;
			pq.emplace(-d[idx], idx);
		}
	}
}