Bellman-Ford y aristas negativas
Gestione valores negativos y detecte ciclos
Bellman-Ford y aristas negativas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Cuándo falla Dijkstra
Dijkstra confía en que una distancia extraída es definitiva, pero una arista negativa puede hacer que una ruta sea más barata después. Por eso falla.
Conozca Bellman-Ford
Bellman-Ford admite pesos negativos en las aristas. Es más lento que Dijkstra, pero resulta fiable cuando no se puede confiar en la lógica voraz.
La operación central
Repite la relajación de todas las aristas: si dist[u] más el peso de la arista es menor que dist[v], actualiza dist[v] con ese valor más pequeño.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wCuántas rondas realizar
Un camino más corto utiliza como máximo V menos 1 aristas, por lo que V-1 rondas de relajación de todas las aristas bastan para establecer todas las distancias.
for _ in range(n - 1):
relax_all_edges()Inicialice las distancias
Comience con todas las distancias en infinito, excepto la del origen, que debe ser cero, exactamente como en Dijkstra.
dist = [float('inf')] * n
dist[src] = 0Una pasada completa
En cada pasada, recorra una vez la lista completa de aristas y relaje cada arista. Las mejoras se propagan hacia fuera un salto por pasada.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wPor qué V-1 es suficiente
Después de k pasadas, todos los caminos más cortos que utilizan k aristas son correctos. Tras V-1 pasadas, todos los caminos más cortos simples han terminado.
La pasada adicional
Ejecute una pasada más. Si alguna distancia aún disminuye, algo sigue abaratándose, lo que indica un ciclo negativo.
Detección de ciclos negativos
Un ciclo negativo significa que no existe un camino más corto finito, ya que puede recorrerlo indefinidamente para reducir el costo sin límite.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'El tiempo de ejecución
Relaja E aristas durante V pasadas, por lo que Bellman-Ford se ejecuta en O(V * E), un costo adecuado para grafos pequeños o medianos.
Dijkstra o Bellman-Ford
Elija Dijkstra para pesos no negativos y mayor velocidad. Elija Bellman-Ford cuando haya pesos negativos o deba detectar un ciclo problemático.
Comprobación rápida
Después de V-1 pasadas, una distancia sigue disminuyendo en una pasada más. ¿Qué significa?
Repaso: Bellman-Ford
Relaje todas las aristas durante V-1 pasadas y luego haga una más para detectar ciclos negativos. Es O(V*E), pero funciona donde Dijkstra no puede. ✅
Preguntas frecuentes
¿La lección «Bellman-Ford y aristas negativas» es gratis?
Sí — el texto completo de «Bellman-Ford y aristas negativas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Bellman-Ford y aristas negativas»?
Gestione valores negativos y detecte ciclos Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Bellman-Ford y aristas negativas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Dijkstra con un heap
- BFS 0-1 con una deque
- Bellman-Ford y aristas negativas
- Floyd-Warshall para todos los pares