Sesión 28: Grokking Algorithms (Capítulo 7) — Algoritmo de Dijkstra y Consolidación de Semana 4#

Navegación rápida:

• ← Sesión 27: CTCI Ch4 — Check Subtree y Paths with Sum
• Sesión 29: Evaluación — Arrays, Strings y Two Pointers →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_28.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Culminamos la Semana 4 dominando el algoritmo de caminos mínimos más célebre de la computación: el algoritmo voraz de Edsger Dijkstra. Consulta el Glosario Maestro y la Guía de Diagramas.

Grafo Ponderado (Weighted Graph)#

• (a) En palabras simples (intuición): Un mapa de carreteras donde cada tramo tiene un letrero con el costo del peaje o el tiempo de viaje en minutos. Una carretera corta pero llena de baches puede tardar 2 horas, mientras que una autopista más larga pero sin tráfico puede tardar 30 minutos.
• (b) Definición técnica paso a paso: Grafo G = (V, E, w) donde cada arista (u, v) ∈ E tiene asociado un valor numérico real w(u, v) denominado peso, costo o capacidad. En el algoritmo estándar de Dijkstra, todos los pesos deben ser estrictamente no negativos (w ≥ 0).
• (c) Cómo funciona en Rust (memoria y tipos): La lista de adyacencia se tipa como Vec<Vec<(usize, u64)>>, donde cada vecino almacena una tupla con el identificador del nodo contiguo y el peso entero de la arista.
• (d) Error típico de Junior: Usar BFS simple en un grafo ponderado; BFS solo cuenta el número de aristas y elegirá rutas lentas o costosas solo porque tienen menos saltos.

Algoritmo de Dijkstra (Estrategia Greedy con Min-Heap)#

• (a) En palabras simples (intuición): Una mancha de aceite que se expande sobre una superficie irregular. El aceite siempre avanza primero hacia el desnivel más cercano y accesible en cada milisegundo, asegurando que el frente de avance sea siempre el más corto posible.
• (b) Definición técnica paso a paso: Algoritmo de camino más corto desde un único origen (Single-Source Shortest Path) para grafos con pesos no negativos. Emplea una estrategia voraz (Greedy): en cada iteración extrae de una cola de prioridad el nodo con la menor distancia tentativa acumulada, garantizando que dicha distancia ya es definitiva e inmejorable.
• (c) Cómo funciona en Rust (memoria y tipos): Utiliza std::collections::BinaryHeap<Reverse<(u64, usize)>>, logrando extraer el mínimo en O(log V) tiempo.
• (d) Error típico de Junior: Intentar aplicar Dijkstra en grafos con pesos negativos; la premisa voraz se rompe y el algoritmo produce distancias incorrectas o entra en bucles infinitos.

Relajación de Aristas (Edge Relaxation)#

• (a) En palabras simples (intuición): Descubrir un atajo en Google Maps. Si creías que llegar a la gasolinera costaba 10 minutos, pero descubres que yendo por la calle B cuesta 4 minutos y desde allí a la gasolinera son 2 minutos (4 + 2 = 6), actualizas de inmediato tu ruta porque 6 es menor que 10.
• (b) Definición técnica paso a paso: Operación fundamental donde, al procesar una arista dirigida u → v con peso w, se comprueba si la distancia conocida hasta v puede mejorarse pasando a través de u:

• (c) Cómo funciona en Rust (memoria y tipos): Se evalúa con aritmética saturada segura (curr_dist.saturating_add(weight)) para prevenir desbordamientos de enteros.
• (d) Error típico de Junior: No insertar la nueva distancia mejorada al Min-Heap tras la relajación.

Min-Heap con BinaryHeap<Reverse<(u64, usize)>> en Rust#

• (a) En palabras simples (intuición): Una balanza que siempre pone arriba al objeto más pesado. Si quieres que ponga arriba al más liviano, multiplicas todos los pesos por -1 o usas un espejo que invierta la comparación.
• (b) Definición técnica paso a paso: La estructura estándar BinaryHeap de Rust implementa un Max-Heap por diseño. Para transformarla en un Min-Heap sin redefinir traits manualmente, se envuelve el elemento en el adaptador std::cmp::Reverse, el cual invierte la lógica del trait Ord.
• (c) Cómo funciona en Rust (memoria y tipos): Reverse((dist, node)) almacena la tupla contigua en un vector en el Heap con cero penalización de rendimiento en silicio.
• (d) Error típico de Junior: Olvidar Reverse y usar BinaryHeap puro; Dijkstra procesará primero los caminos más largos y costosos en lugar de los más cortos.

Descarte Perezoso de Distancias Obsoletas (Lazy Deletion)#

• (a) En palabras simples (intuición): Si recibes una carta vieja diciendo que tu pedido llegará el viernes, pero ayer ya recibiste un mensaje nuevo diciendo que llega hoy jueves, simplemente tiras la carta vieja a la basura sin leerla.
• (b) Definición técnica paso a paso: En Rust, BinaryHeap no implementa la operación decrease_key tradicional de los montículos de Fibonacci. Cuando se encuentra una distancia mejor hacia un nodo v, simplemente se inserta un nuevo par (nueva_dist, v) al heap. Al extraer un par más adelante, si curr_dist > distances[curr_node], significa que esta entrada es un residuo obsoleto y se descarta con continue en O(1).
• (c) Cómo funciona en Rust (memoria y tipos): La comprobación if curr_dist > distances[curr_node] { continue; } evita re-procesar los vecinos de un nodo que ya fue resuelto con un camino más corto.
• (d) Error típico de Junior: Omitir esta comprobación; el algoritmo procesará nodos obsoletos múltiples veces, degradando el rendimiento asintótico.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

¿Por Qué BFS Falla en Grafos Ponderados?#

Consideremos el siguiente grafo:

           (A)
          /   \
      10 /     \ 1
        /       v
    (S) --------> (T)
           100

• Ruta 1: S -> T (1 arista, peso = 100).
• Ruta 2: S -> A -> T (2 aristas, peso = 10 + 1 = 11).

¿Qué hace BFS?

1. BFS explora la capa 1 (distancia de 1 arista): descubre a A (peso 10) y a T (peso 100).
2. Como T fue alcanzado en la capa 1, BFS concluye que S -> T es la ruta óptima porque solo requirió 1 arista.

¡BFS ignoró por completo que la Ruta 2, a pesar de tener 2 aristas, tiene un costo físico 9 veces menor (11 < 100)! BFS optimiza número de saltos, jamás costo acumulado. Para costo acumulado se requiere Dijkstra.

Demostración de Correctitud de Dijkstra (La Invariante Greedy)#

¿Por qué Dijkstra garantiza que cuando un nodo u se extrae del Min-Heap, su distancia acumulada dist[u] es la mínima absoluta definitiva en todo el grafo? Demostración por contradicción:

1. Supongamos que existe una ruta alternativa no explorada R_{alt} desde S hasta u con un costo total menor que dist[u].
2. Como la ruta alternativa comienza en S y llega a u, debe abandonar el conjunto de nodos ya resueltos pasando por algún nodo de frontera F que se encuentra actualmente en el Min-Heap.
3. Como todos los pesos son no negativos (w ≥ 0):
   Costo(R_{alt}) ≥ dist[F]
4. Pero el algoritmo extrajo a u del Min-Heap antes que a F. Por la propiedad de orden del Min-Heap:
   dist[u] ≤ dist[F]
5. Encadenando las desigualdades:
   dist[u] ≤ dist[F] ≤ Costo(R_{alt}) ⟹ mathbf{dist[u] ≤ Costo(R_{alt})}

¡Esto contradice la suposición inicial de que la ruta alternativa era estrictamente menor! Por consiguiente, dist[u] es definitiva.

La Catástrofe de los Pesos Negativos#

¿Por qué falla el razonamiento anterior si permitimos un peso negativo (ej. w = -50)? En el paso 3 de la demostración anterior, asumimos que Costo(R_{alt}) ≥ dist[F] porque sumar pesos solo puede aumentar o mantener la distancia. Si existe una arista con peso negativo más adelante en el camino, el costo futuro puede reducirse drásticamente, haciendo que un camino que parecía más largo en la frontera resulte ser más corto al final. Dijkstra ya habrá marcado a u como resuelto y nunca reevaluará sus caminos, produciendo resultados erróneos. Para grafos con aristas negativas se debe utilizar Bellman-Ford (O(V · E)).

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Diagramas de Arquitectura#

• Gráfico SVG vectorial: ![Visualización del Día 28 y Memoria en Rust](../diagrams/sesiones/dia_28.svg)
• Código fuente del diagrama: Fuente Mermaid

Grafo Ponderado de Grokking Algorithms y Relajación#

flowchart LR
    S["(0) Start"] -->|"w=6"| A["(1) A"]
    S -->|"w=2"| B["(2) B"]
    B -->|"w=3"| A
    B -->|"w=5"| F["(3) Fin"]
    A -->|"w=1"| F

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Ejecución de Dijkstra sobre el grafo de Grokking:

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame dijkstra                |               | distances: Vec<u64>                  |
|   n: 4                        |               | [ 0, inf, inf, inf ]                 |
|   distances: Vec<u64> --------+-------------->+--------------------------------------+
|   parents: Vec<Option<usize>>-+------+        | parents: [ None, None, None, None ]  |
|   min_heap: BinaryHeap -------+---+  |        +--------------------------------------+
+-------------------------------+   |  +-------> min_heap: BinaryHeap<Reverse<(u64, usize)>>
                                    +----------> [ Reverse((0, 0)) ] (Start con costo 0)

Iteración 1: Extrae Reverse((0, 0)) (Nodo 0).
- Vecino 1: 0 + 6 = 6 < inf -> dist[1]=6, parent[1]=Some(0), push(Reverse((6, 1)))
- Vecino 2: 0 + 2 = 2 < inf -> dist[2]=2, parent[2]=Some(0), push(Reverse((2, 2)))
Heap: [ Reverse((2, 2)), Reverse((6, 1)) ]

Iteración 2: Extrae Reverse((2, 2)) (Nodo 2 con costo 2).
- Vecino 1 (A): 2 + 3 = 5 < dist[1] (6) -> ¡RELAJACIÓN EXITOSA!
  dist[1] se actualiza a 5, parent[1]=Some(2), push(Reverse((5, 1))).
- Vecino 3 (Fin): 2 + 5 = 7 < inf -> dist[3]=7, parent[3]=Some(2), push(Reverse((7, 3))).
Heap: [ Reverse((5, 1)), Reverse((6, 1)), Reverse((7, 3)) ]

Iteración 3: Extrae Reverse((5, 1)) (Nodo 1 con costo 5).
- Vecino 3 (Fin): 5 + 1 = 6 < dist[3] (7) -> ¡RELAJACIÓN EXITOSA!
  dist[3] se actualiza a 6, parent[3]=Some(1), push(Reverse((6, 3))).
Heap: [ Reverse((6, 3)), Reverse((6, 1)), Reverse((7, 3)) ]

Iteración 4: Extrae Reverse((6, 3)) (Nodo 3 con costo 6).
- Destino alcanzado con costo definitivo 6.

Iteración 5: Extrae Reverse((6, 1)).
- curr_dist (6) > dist[1] (5) -> ¡DESCARTE PEREZOSO! Se ignora con continue en O(1).

4. Matriz de Consolidación de la Semana 4 (Árboles y Grafos)#

5. Implementación Canónica en Rust + Comparativa con Python#

Implementación Canónica en Rust (practica-rust/dia_28.rs)#

//! Día 28: Algoritmo de Dijkstra y Consolidación de Semana 4 en Rust.
//! Compilable y verificable con `rustc --test`.

use std::cmp::Reverse;
use std::collections::BinaryHeap;

#[derive(Debug, Clone)]
pub struct WeightedGraph {
    num_vertices: usize,
    adj: Vec<Vec<(usize, u64)>>,
    directed: bool,
}

impl WeightedGraph {
    pub fn new(num_vertices: usize, directed: bool) -> Self {
        Self {
            num_vertices,
            adj: vec![Vec::new(); num_vertices],
            directed,
        }
    }

    pub fn num_vertices(&self) -> usize { self.num_vertices }

    pub fn add_edge(&mut self, u: usize, v: usize, weight: u64) {
        assert!(u < self.num_vertices && v < self.num_vertices);
        self.adj[u].push((v, weight));
        if !self.directed {
            self.adj[v].push((u, weight));
        }
    }

    pub fn neighbors(&self, u: usize) -> &[(usize, u64)] {
        &self.adj[u]
    }
}

#[derive(Debug, PartialEq, Eq)]
pub struct DijkstraResult {
    pub distances: Vec<u64>,
    pub parents: Vec<Option<usize>>,
}

/// Algoritmo de Dijkstra con Min-Heap en O((V + E) log V).
pub fn dijkstra(graph: &WeightedGraph, start: usize) -> DijkstraResult {
    let n = graph.num_vertices();
    let mut distances = vec![u64::MAX; n];
    let mut parents: Vec<Option<usize>> = vec![None; n];

    let mut min_heap = BinaryHeap::new();
    distances[start] = 0;
    min_heap.push(Reverse((0, start)));

    while let Some(Reverse((curr_dist, curr_node))) = min_heap.pop() {
        if curr_dist > distances[curr_node] {
            continue; // Descarte perezoso de distancias obsoletas
        }

        for &(neighbor, weight) in graph.neighbors(curr_node) {
            let new_dist = curr_dist.saturating_add(weight);
            if new_dist < distances[neighbor] {
                distances[neighbor] = new_dist;
                parents[neighbor] = Some(curr_node);
                min_heap.push(Reverse((new_dist, neighbor)));
            }
        }
    }

    DijkstraResult { distances, parents }
}

/// Reconstrucción de la ruta más corta.
pub fn reconstruct_path(parents: &[Option<usize>], start: usize, target: usize) -> Option<Vec<usize>> {
    if start == target { return Some(vec![start]); }
    if target >= parents.len() || parents[target].is_none() { return None; }

    let mut path = Vec::new();
    let mut curr = Some(target);
    while let Some(node) = curr {
        path.push(node);
        if node == start { break; }
        curr = parents[node];
    }
    if path.last() != Some(&start) { return None; }
    path.reverse();
    Some(path)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_dijkstra() {
        let mut g = WeightedGraph::new(4, true);
        g.add_edge(0, 1, 6);
        g.add_edge(0, 2, 2);
        g.add_edge(2, 1, 3);
        g.add_edge(2, 3, 5);
        g.add_edge(1, 3, 1);

        let res = dijkstra(&g, 0);
        assert_eq!(res.distances[3], 6);
        assert_eq!(reconstruct_path(&res.parents, 0, 3), Some(vec![0, 2, 1, 3]));
    }
}

Implementación Canónica en Python (practica/dia_28_dijkstra_shortest_path.py)#

import heapq
from typing import Dict, List, Optional, Set, Tuple

def dijkstra_shortest_path(
    graph: Dict[int, List[Tuple[int, float]]], num_vertices: int, start: int
) -> Tuple[List[float], List[Optional[int]]]:
    """Algoritmo de Dijkstra con Min-Heap en O((V + E) log V)."""
    distances = [float("inf")] * num_vertices
    distances[start] = 0.0
    parents: List[Optional[int]] = [None] * num_vertices

    pq: List[Tuple[float, int]] = [(0.0, start)]
    visited: Set[int] = set()

    while pq:
        curr_dist, curr = heapq.heappop(pq)
        if curr in visited:
            continue
        visited.add(curr)

        for neighbor, weight in graph.get(curr, []):
            if neighbor in visited:
                continue
            new_dist = curr_dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                parents[neighbor] = curr
                heapq.heappush(pq, (new_dist, neighbor))

    return distances, parents

6. Las 3 Trampas Clásicas en Entrevistas#

1. Aplicar Dijkstra a Grafos con Pesos Negativos: - Dijkstra asume que una vez que un nodo se extrae del Min-Heap, su distancia acumulada es final e irrevocable. Aristas negativas rompen esta invariante greedy. Menciona siempre Bellman-Ford si los pesos pueden ser negativos.
2. Olvidar el Descarte Perezoso de Entradas Obsoletas: - Sin if curr_dist > distances[curr_node] continue, el algoritmo procesará nodos múltiples veces con distancias que ya fueron mejoradas por caminos posteriores, disparando el tiempo de ejecución.
3. Desbordamiento de Enteros al Sumar Infinitos: - Si inicializas distancias con u64::MAX e intentas sumar dist[u] + weight, el procesador causará un pánico por desbordamiento aritmético (integer overflow). Usa siempre aritmética saturada curr_dist.saturating_add(weight).

7. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

if curr_dist > distances[curr_node] { continue; }

8. Puente a LeetCode y Práctica de Código#

1. LeetCode 743 — Network Delay Time (Medium): - Dijkstra puro sobre grafos dirigidos ponderados con descarte perezoso.
2. LeetCode 787 — Cheapest Flights Within K Stops (Medium): - Camino de costo mínimo con restricción estricta de saltos (Dijkstra modificado con estado de paradas o Bellman-Ford).
3. LeetCode 1631 — Path With Minimum Effort (Medium): - Dijkstra aplicado sobre matrices 2D donde el costo es la diferencia máxima de alturas en la trayectoria.

9. Tarea en Papel para Hoy#

Toma una hoja de papel y dibuja un grafo ponderado de 5 nodos ($0$ al $4$) con aristas: 0 -> 1 (peso 4), 0 -> 2 (peso 2), 2 -> 1 (peso 1), 1 -> 3 (peso 2), 2 -> 4 (peso 8), 3 -> 4 (peso 3).

1. Traza a mano el algoritmo de Dijkstra desde el origen 0 hasta todos los nodos.
2. Dibuja la tabla de distances y el contenido del min_heap en cada extracción.
3. Observa cómo el nodo 1 es relajado de distancia 4 a distancia 3 pasando a través del nodo 2.
4. Reconstruye el camino más corto hacia el nodo 4 y anota su costo total.

Navegación:

• ← Volver a Sesión 27: CTCI Ch4 — Check Subtree y Paths with Sum
• Avanzar a Sesión 29: Evaluación — Arrays, Strings y Two Pointers →