Camino más corto de Dijkstra
Caminos de menor costo sobre aristas con pesos no negativos.
BFS con una priority queue en lugar de una cola simple.
Los pesos rompen BFS
- BFS encuentra menos ARISTAS; con pesos eso ≠ más barato
- Una arista larga puede costar más que tres cortas
- Solución: expandir el nodo más cercano por PESO total, con un min-heap
- Asentar al sacar: la primera vez que un nodo sale del heap, su distancia es definitiva
Mira las distancias asentarse
Números en los nodos = distancia tentativa (∞ → cae conforme se relajan las aristas).
Verde = asentado · azul = frontera · números grises = pesos de las aristas.
La arista directa es una trampa
- Arista directa 0→6: peso 10
- Dijkstra toma 0→1→3→6: costo 3
- Más barato ≠ menos saltos
- Grafos aleatorios: el camino de BFS ~25% más caro; el peor caso, sin tope
Relajación + no negatividad
- Relajar:
if dist[u]+w < dist[v]: dist[v] = dist[u]+w (solo baja, nunca sube)
- Es correcto porque pesos no negativos ⇒ asentado = definitivo
- UNA arista negativa lo rompe → Bellman-Ford
- O((V+E) log V) con un binary heap
Para llevar
El capítulo de heaps rinde frutos aquí: la priority queue es todo el truco.
networkx.single_source_dijkstra en producción; A* y Prim son esto + una idea.
Siguiente: Bellman-Ford, para pesos negativos.