18 · Grafos II: Dijkstra y DAGs
Grafos y consultas · Ruta de Aprendizaje
Antes de empezar. BFS: 16 - Distancias en grafos; pares y heap: 06 - Conjuntos, mapas y pares y 11 - Colas de prioridad. Para el conteo de caminos en un DAG, 14 - Programación dinámica I.
🎯 Objetivos
Al terminar este módulo sabes:
- Implementar Dijkstra con cola de prioridad (la promesa del módulo 16, cumplida).
- Ordenar topológicamente un grafo dirigido y detectar ciclos.
- Ubicar Bellman-Ford y Floyd-Warshall en el mapa (cuándo cada uno).
📖 La lección
Aquí hay dos herramientas: distancias con pesos no negativos y ordenar dependencias sin ciclos. Sus ejemplos son independientes: el primero guarda pares (vecino,peso); el segundo, solo vecinos.
Dijkstra: BFS con pesos
Queremos ir desde 1 a los otros nodos. Hay aristas dirigidas 1→2 de
costo 10, 1→3 de costo 1 y 3→2 de costo 1. Descubrir el 2 por la arista
directa nos da una propuesta de costo 10, no una respuesta definitiva:
pasar por 3 cuesta solo 2.
Relajar una arista u→v consiste en proponer llegar a v desde u, por
costo dist[u] + peso. Solo cambiamos dist[v] si mejora la mejor propuesta
que teníamos. dist guarda esas mejores propuestas; inicialmente solo
sabemos llegar al origen, con costo cero.
| Nodo que procesamos | Propuestas nuevas o mejoradas | Pendientes (costo, nodo) |
|---|---|---|
| 1, con costo 0 | a 2 por 10; a 3 por 1 | (1,3), (10,2) |
| 3, con costo 1 | a 2 por 1+1=2 | (2,2), (10,2) |
| 2, con costo 2 | ninguna | (10,2) |
Procesamos siempre la propuesta de menor costo: para eso sirve el min-heap.
La propuesta (10,2) sigue en él, pero está obsoleta: dist[2] ya vale 2.
Cuando salga la ignoramos. Marcar el nodo como definitivo al descubrirlo,
como hacíamos en BFS sin pesos, habría impedido esa mejora.
Con pesos no negativos, una propuesta vigente de menor costo sí puede cerrarse al extraerla: un camino que todavía debe recorrer aristas no puede abaratarse atravesándolas. Más abajo justificaremos esa garantía. Ahora el bucle sigue esas decisiones: extraer, descartar si es antigua y proponer mejoras a los vecinos.
Este ejemplo parte del nodo 1, con n >= 1 y nodos 1..n. Cada
ady[u] guarda pares (vecino, peso), mientras el heap guarda
(distancia, nodo). auto [d, u] da nombre a ambos componentes del par.
Los pesos son no negativos y suponemos que cada distancia válida y cada
suma examinada es menor que INF = 4·10¹⁸.
// supone: int n; vector<vector<pair<int,long long>>> ady; // ady[u] = {vecino, peso}
const long long INF = 4e18; // "todavía no alcanzado"
vector<long long> dist(n + 1, INF);
// min-heap de (distancia, nodo): siempre entrega el más cercano
priority_queue<pair<long long,int>, vector<pair<long long,int>>,
greater<pair<long long,int>>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // entrada vieja: ignorar
for (auto [v, w] : ady[u])
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}Como segundo ejemplo, sigue la traza en este grafo de cinco nodos (la cola muestra pares (distancia, nodo)):
Si el diagrama no cabe, deslízalo horizontalmente.
| saca de la cola | ¿obsoleta? | relaja | dist después (1..5) | cola después |
|---|---|---|---|---|
| (0, 1) | no | 2: 4 · 3: 1 | 0, 4, 1, ∞, ∞ | (1,3) (4,2) |
| (1, 3) | no | 2: 1+2 = 3 < 4 ✓ · 4: 9 · 5: 11 | 0, 3, 1, 9, 11 | (3,2) (4,2) (9,4) (11,5) |
| (3, 2) | no | 4: 3+5 = 8 < 9 ✓ | 0, 3, 1, 8, 11 | (4,2) (8,4) (9,4) (11,5) |
| (4, 2) | sí: 4 > dist[2] = 3 | — | (8,4) (9,4) (11,5) | |
| (8, 4) | no | 5: 8+3 = 11, no mejora | 0, 3, 1, 8, 11 | (9,4) (11,5) |
| (9, 4) | sí: 9 > 8 | — | (11,5) | |
| (11, 5) | no | — | 0, 3, 1, 8, 11 | vacía |
Dos cosas que la traza deja a la vista. Cuando dist[2] mejoró de 4 a 3, la
entrada (4, 2) no se borró de la cola (un heap no sabe borrar del
medio): quedó ahí como fósil y se descartó al salir. Y una vez que un nodo
sale de la cola con su distancia definitiva, ya nada la cambia — esa es la
promesa que los pesos negativos rompen.
¿Por qué una extracción vigente es definitiva? Supón que queda un camino más barato hacia el nodo extraído u. En ese camino, el primer nodo todavía no procesado recibió una propuesta al procesar su predecesor. Con pesos no negativos, esa propuesta no supera el costo del camino completo, y por tanto sería menor que dist[u]. La cola habría extraído esa propuesta antes que u: contradicción. Un peso negativo rompe justamente esa comparación.
O((n+m) log n). Dos cláusulas del contrato: pesos no negativos (con
negativos, la garantía se rompe), y el if (d > dist[u]) continue; que
descarta entradas obsoletas de la cola — sin él, TLE. (La forma
auto [d, u] = pq.top(); desempaqueta el par en dos variables de una vez;
equivale a leer .first y .second por separado.) Detalles y demostración
en Dijkstra.
Por qué la promesa exige pesos no negativos, en un dibujo:
Si el diagrama no cabe, deslízalo horizontalmente.
DAGs y orden topológico
En un grafo dirigido sin ciclos (DAG) existe un orden donde toda arista va “hacia adelante”: el orden topológico (cursos con prerrequisitos, tareas con dependencias). Se construye pelando nodos sin aristas entrantes (Orden topológico (Kahn)) — y si el proceso se atasca antes de terminar, acabas de detectar un ciclo.
Si el diagrama no cabe, deslízalo horizontalmente.
Sobre un DAG en orden topológico, los caminos (más largos, más cortos, conteos) se calculan con una pasada de DP — la primera boda entre DP y grafos: al procesar cada nodo en ese orden, todos sus predecesores ya tienen su respuesta lista.
Construir el orden paso a paso: Kahn
El grado de entrada de un nodo cuenta cuántas aristas llegan a él.
Un nodo con grado cero puede ir primero: no depende de tareas pendientes.
Al retirarlo, quitamos sus aristas y liberamos nuevas tareas.
Aquí ady[u] guarda destinos sin pesos, con nodos 1..n.
Para las aristas
1 → 3, 2 → 3, 3 → 4, los grados son 0, 0, 2, 1.
Primero están libres 1 y 2. Retirar solo el 1 no libera el 3; retirar
el 2 también reduce su grado a cero. Luego salen 3 y 4. Así obtenemos
1, 2, 3, 4; 2, 1, 3, 4 también sería válido.
| Nodo retirado (ejemplo de cuatro tareas) | Grado de entrada de 3 | Grado de entrada de 4 | Nuevos libres |
|---|---|---|---|
| ninguno | 2 | 1 | 1,2 |
| 1 | 1 | 1 | ninguno |
| 2 | 0 | 1 | 3 |
| 3 | 0 | 0 | 4 |
Se encola al pasar a cero, cuando todos sus prerrequisitos han salido.
En el código, --entrada[v] resta uno antes de comparar con cero.
// supone: int n; vector<vector<int>> ady;
vector<int> entrada(n + 1, 0), orden;
for (int u = 1; u <= n; u++)
for (int v : ady[u]) entrada[v]++;
queue<int> libres;
for (int u = 1; u <= n; u++)
if (entrada[u] == 0) libres.push(u);
while (!libres.empty()) {
int u = libres.front(); libres.pop();
orden.push_back(u);
for (int v : ady[u])
if (--entrada[v] == 0) libres.push(v);
}
bool hay_ciclo = ((int)orden.size() != n);Si quedan nodos pero ninguno está libre, hay una cadena de dependencias que vuelve a un nodo anterior: un ciclo. El orden parcial no sirve como orden topológico del grafo completo. Se procesa cada nodo y arista una vez: O(n + m).
Una DP sobre ese orden. Para contar caminos desde el nodo 1, comienza
con formas[1] = 1 (el camino vacío) y el resto en cero. Por cada arista
u → v, agrega formas[u] a formas[v], siguiendo el orden topológico.
En el ejemplo, las cantidades finales para 1..4 son 1, 0, 1, 1.
Si agregamos 1 → 2, son 1, 1, 2, 2: los dos caminos hacia 3 se
pueden extender hacia 4. Cada aporte llega antes de procesar su destino.
Los conteos pueden crecer mucho; usa el módulo que pida el problema o un
tipo que alcance para su respuesta.
El mapa completo de caminos mínimos
| Situación | Algoritmo | Costo |
|---|---|---|
| pesos iguales y positivos | BFS | O(n+m) |
| pesos ≥ 0 | Dijkstra | O((n+m) log n) |
| pesos negativos; detectar ciclos negativos alcanzables | Bellman-Ford | O(n·m) |
| todas las parejas (n chico) | Floyd-Warshall | O(n³) |
Si un ciclo negativo alcanzable puede llevar al destino, repetirlo reduce el costo sin límite: no existe distancia mínima finita a ese destino. Bellman-Ford permite detectar esa situación. Floyd-Warshall y reconstruir un ciclo dirigido son ampliaciones; Kahn detecta que hay ciclo, pero su código no devuelve sus vértices.
🏋️ Práctica
Práctica directa: Pasos y costo
Grafo dirigido: 1→2 cuesta 10, 1→3 cuesta 1 y 3→2 cuesta 1. Imprime la menor distancia desde 1 a cada nodo: 0 2 1.
Idea para comprobar tu solución
La propuesta directa a 2 es 10 y mejora a 2 al procesar 3. Como variante sin pesos, un orden topológico válido es 1,3,2.
Variación: Una conexión aparentemente conveniente
En un grafo dirigido hay aristas 0→1 de costo 10, 0→2 de costo 2 y 2→1 de costo 3. Calcula el costo mínimo de 0 a 1. ¿Serviría buscar solo la menor cantidad de aristas?
Una pista, si la necesitas
Compara el enlace directo con el camino que usa dos enlaces.
Contrastar el razonamiento
El costo mínimo es 5 por 0→2→1. BFS elegiría el enlace directo por tener una sola arista y no resolvería la pregunta de costo. Con pesos no negativos, Dijkstra considera el costo acumulado.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Los dos primeros problemas aplican las herramientas desarrolladas aquí. Los otros dos son ampliaciones: consulta las fichas de Floyd-Warshall o de detección y reconstrucción de ciclos antes de intentarlos.
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Shortest Routes I (CSES 1671) | ★★★ (—) | Dijkstra, tal cual |
| 2 | Course Schedule (CSES 1679) | ★★★ (—) | orden topológico |
| 3 | Shortest Routes II (CSES 1672) | ★★★ (—) | Floyd-Warshall (n chico, todas las parejas) |
| 4 | ⭐ Round Trip II (CSES 1678) | ★★★★ (—) | encontrar (y reconstruir) un ciclo dirigido |
Desafío OCI (en español)
| Problema | Fase | Qué practica |
|---|---|---|
| ⭐ Transbordo en el aeropuerto | Nacional 2017 | Dijkstra con trenes de horario fijo |
Para pensar: una distancia que mejora después de salir
Considera las aristas dirigidas S → A de peso 2, S → B de peso 5 y
B → A de peso −4. ¿Qué distancia tiene A cuando sale por primera vez de
la cola de prioridad? ¿Cuál es su distancia mínima real?
Ver razonamiento
Sale con 2 antes que B, pero el camino
S → B → Acuesta 1. El peso negativo rompe la garantía de que la primera extracción de un nodo con su mejor distancia conocida ya es definitiva. Una versión que lo cierre para siempre daría una respuesta incorrecta. El código de esta lección permite reinsertarlo y en este ejemplo llega a 1, pero deja de tener la garantía de eficiencia de Dijkstra. Como este grafo es un DAG, el orden topológicoS, B, Apermite calcular las distancias en una pasada incluso con ese peso.
← 17 - Sumas de prefijos · Ruta de Aprendizaje · 19 - Union-Find (DSU) →