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 procesamosPropuestas nuevas o mejoradasPendientes (costo, nodo)
1, con costo 0a 2 por 10; a 3 por 1(1,3), (10,2)
3, con costo 1a 2 por 1+1=2(2,2), (10,2)
2, con costo 2ninguna(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)):

412583101dist 02dist 33dist 14dist 85dist 11por 1→3 (1) y 3→2 (2), llegar a 2 cuesta 3: mejor que la arista directa de 4en grueso, un árbol elegido; 1→3→5 también cuesta 11

Si el diagrama no cabe, deslízalo horizontalmente.

saca de la cola¿obsoleta?relajadist después (1..5)cola después
(0, 1)no2: 4 · 3: 10, 4, 1, ∞, ∞(1,3) (4,2)
(1, 3)no2: 1+2 = 3 < 4 ✓ · 4: 9 · 5: 110, 3, 1, 9, 11(3,2) (4,2) (9,4) (11,5)
(3, 2)no4: 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)no5: 8+3 = 11, no mejora0, 3, 1, 8, 11(9,4) (11,5)
(9, 4)sí: 9 > 8—(11,5)
(11, 5)no—0, 3, 1, 8, 11vací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:

25−4sabPrimero sale a con dist 2:¿es ya su distancia definitiva?pero s→b→a cuesta 5 − 4 = 1la promesa depende de que ningún pasohaga bajar el costo: pesos ≥ 0con negativos: Bellman-Ford

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.

123546entran 0entran 0entran 2entran 1entran 1entran 2orden topológico: 1 2 3 5 4 6 (o 2 1 5 3 4 6: no es único)Kahn: saca los que no tienen aristas entrantes, réstale 1 a sus destinos y repite;si faltan nodos y ninguno queda en 0, hay 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 3Grado de entrada de 4Nuevos libres
ninguno211,2
111ninguno
2013
3004

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ónAlgoritmoCosto
pesos iguales y positivosBFSO(n+m)
pesos ≥ 0DijkstraO((n+m) log n)
pesos negativos; detectar ciclos negativos alcanzablesBellman-FordO(n·m)
todas las parejas (n chico)Floyd-WarshallO(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.

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?

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.

#ProblemaDificultadQué practica
1Shortest Routes I (CSES 1671)★★★ (—)Dijkstra, tal cual
2Course Schedule (CSES 1679)★★★ (—)orden topológico
3Shortest 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)

ProblemaFaseQué practica
⭐ Transbordo en el aeropuertoNacional 2017Dijkstra 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?


← 17 - Sumas de prefijos · Ruta de Aprendizaje · 19 - Union-Find (DSU) →