Dijkstra
Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 18 de la Ruta de Aprendizaje.
El problema: llegar con el menor costo total
Tenemos lugares conectados por caminos con costos no negativos, incluido cero. Queremos la distancia mínima desde A a cada lugar: la suma de los costos del recorrido, no la cantidad de aristas. Un grafo guarda los lugares como vértices y cada conexión como una arista con peso.
En el ejemplo todas las aristas tienen ambos sentidos. A–B cuesta 7, A–C cuesta 2, C–B cuesta 1, C–D cuesta 6 y B–D cuesta 3. Ir directamente a B cuesta 7, pero A–C–B cuesta solo 3.
Si el diagrama no cabe, deslízalo horizontalmente.
Distancias tentativas y relajación
Guardamos para cada vértice el costo del mejor camino encontrado hasta ahora. Al principio A vale 0 y el resto vale ∞, que significa «todavía sin camino conocido».
Si conocemos un camino de costo dist[u] hasta u y una arista u→v de costo w,
podemos llegar a v pagando dist[u] + w. Si eso mejora su valor anterior,
lo reemplazamos. Esta comparación y posible mejora se llama relajar una arista.
La decisión de Dijkstra es procesar siempre el vértice pendiente con menor distancia tentativa. Para encontrarlo usamos una cola de prioridad mínima: una estructura que inserta candidatos y extrae el de menor costo en O(log n). El código de biblioteca se explica en priority_queue (heap).
| Vértice procesado | Distancias A, B, C, D después de relajar sus salidas |
|---|---|
| Inicio | 0, ∞, ∞, ∞ |
| A, costo 0 | 0, 7, 2, ∞ |
| C, costo 2 | 0, 3, 2, 8 |
| B, costo 3 | 0, 3, 2, 6 |
| D, costo 6 | 0, 3, 2, 6 |
Los candidatos viejos de B con costo 7 y D con costo 8 pueden seguir en la cola. Cuando salen, ya no coinciden con la mejor distancia y se ignoran.
Por qué podemos confiar en el menor pendiente
Cuando extraemos u con su distancia vigente, cualquier camino alternativo
que pase por un vértice todavía pendiente empieza a costar al menos dist[u]:
u tenía la menor distancia. Continuar por aristas no negativas no puede reducirla.
Por tanto, ningún camino descubierto más tarde mejorará la distancia de u.
Más formalmente, si existiera un camino más barato, toma su primer vértice
todavía no procesado. Su predecesor ya habría relajado la arista hacia él,
dejando un candidato de costo menor que dist[u]. Habríamos extraído ese
candidato primero. La no negatividad es lo que sostiene el argumento.
Implementación y datos de entrada
vector<long long> dijkstra(int s, const vector<vector<pair<int,int>>>& g) {
const long long INF = 1e18;
vector<long long> dist(g.size(), INF);
priority_queue<pair<long long,int>, vector<pair<long long,int>>,
greater<pair<long long,int>>> pq; // min-heap: el más cercano primero
dist[s] = 0; pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop(); // desempaqueta el par en dos variables
if (d > dist[u]) continue; // entrada obsoleta
for (auto [v, w] : g[u])
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
return dist;
}Cada entrada de g[u] es el par {vecino, peso}. En cambio, la cola almacena
{distancia, vértice} para ordenar por distancia: son dos tipos de pares
con significados diferentes.
Numera A…D como 0…3 y usa
g = {{{1,7},{2,2}}, {{0,7},{2,1},{3,3}}, {{0,2},{1,1},{3,6}}, {{1,3},{2,6}}}
en un vector<vector<pair<int,int>>>. La llamada dijkstra(0,g) devuelve
{0,3,2,6}. En un grafo dirigido añade solo las salidas permitidas;
la misma función sirve sin agregar la arista inversa.
El origen y los vecinos deben ser índices válidos. Esta versión requiere
C++17 por auto [d,u]. Usa pesos int, distancias long long y un centinela
de 10¹⁸: las distancias finitas deben ser menores que él y las sumas calculadas
deben caber en long long. Un vértice inalcanzable conserva ese centinela.
Costos y errores que cambian el algoritmo
Inicializar distancias cuesta O(V). Cada arista puede originar una mejora y una entrada en la cola: esta versión permite O(E) entradas, por lo que el tiempo es O(V + E log(E+1)) y la memoria adicional O(V + E). En grafos simples suele expresarse como O((V+E) log V).
No marques un vértice como definitivo al insertarlo: B se inserta primero con 7, pero luego mejora a 3. La comprobación de entrada obsoleta evita volver a recorrer todas sus salidas con cada candidato viejo.
Los pesos negativos invalidan la demostración y las garantías de costo: esta implementación puede reprocesar vértices y un ciclo negativo alcanzable impide terminar. Para ese caso estudia Bellman-Ford. Si todos los pesos son iguales, BFS es suficiente.
cuando aparece D por primera vez?
No: D aparece con costo 8 desde C, pero mejora a 6 desde B. Si solo buscas un destino, puedes terminar cuando lo extraigas con su distancia vigente, después de descartar entradas obsoletas, bajo las condiciones de Dijkstra.
Práctica en 18 - Grafos II - Dijkstra y DAGs.