Bellman-Ford y ciclos negativos
Realice n-1 pasadas de relajación sobre todas las aristas, detecte ciclos negativos con una pasada final y explique por qué Dijkstra falla con aristas de peso negativo.
Bellman-Ford y ciclos negativos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 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.
Por qué existe Bellman-Ford
Bellman-Ford resuelve el problema del camino más corto desde un único origen, al igual que Dijkstra, pero admite pesos negativos en las aristas. También detecta ciclos negativos: ciclos cuyo peso total es negativo, lo que impide definir un camino más corto finito que los atraviese. Aunque es más lento que Dijkstra, Bellman-Ford es la opción correcta siempre que el grafo pueda contener aristas con pesos negativos.
Relajación: la operación fundamental
Bellman-Ford se basa en una única operación: la relajación. Relajar la arista (u, v, w) significa que, si dist[u] + w < dist[v], se actualiza dist[v] = dist[u] + w. Repetimos la relajación de todas las aristas. La idea clave es que cualquier camino más corto tiene como máximo V-1 aristas (en un grafo sin ciclos negativos). Por tanto, V-1 rondas de relajación de todas las aristas son suficientes para encontrar todos los caminos más cortos.
Implementación de Bellman-Ford
Represente el grafo como una lista de aristas [(u, v, weight)]. Inicialice dist[source] = 0 y todas las demás distancias a inf. Ejecute V-1 rondas y relaje todas las aristas en cada ronda. Cualquier actualización que siga produciéndose en una ronda V indica que existe un ciclo negativo.
def bellman_ford(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
# V-1 relaxation passes
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# V-th pass: detect negative cycle
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # negative cycle exists
return dist
edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0)) # [0, 4, 1, 2]Por qué V-1 pasadas son suficientes
Un camino más corto en un grafo sin ciclos negativos visita cada nodo como máximo una vez, por lo que tiene como máximo V-1 aristas. Después de la ronda 1, los caminos más cortos de 1 salto son óptimos. Después de la ronda 2, los caminos más cortos de 2 saltos son óptimos. Después de V-1 rondas, se han encontrado todos los caminos más cortos, que utilizan como máximo V-1 saltos. Si en la ronda V todavía se actualiza una distancia, el grafo contiene un ciclo negativo alcanzable desde el origen.
Detección de ciclos negativos
Después de V-1 pasadas, realice una pasada adicional sobre todas las aristas. Si alguna arista (u, v, w) cumple dist[u] + w < dist[v], existe un ciclo negativo y el camino más corto hasta algunos nodos es -infinity. Entre las aplicaciones del mundo real se encuentran la detección de oportunidades de arbitraje en el intercambio de divisas (ciclos negativos en grafos con pesos logarítmicos) y la detección de incoherencias en sistemas de restricciones.
def has_negative_cycle(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Nth pass
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return True # negative cycle detected
return False
# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0)) # TrueComparación entre Dijkstra y Bellman-Ford
Dijkstra: O((V+E) log V), requiere pesos no negativos y utiliza un enfoque voraz. Bellman-Ford: O(V × E), admite pesos negativos y detecta ciclos negativos. Para la mayoría de los problemas de entrevistas con pesos no negativos, se prefiere Dijkstra. Cuando aparecen pesos negativos (por ejemplo, «encontrar el camino más corto con aristas de coste negativo» o «detectar arbitraje»), la respuesta es Bellman-Ford. Para grafos densos, el peor caso O(V³) de Bellman-Ford es comparable al de Floyd-Warshall.
Aplicación: vuelos más baratos con Bellman-Ford
Cheapest Flights Within K Stops (LeetCode 787) puede resolverse con una versión modificada de Bellman-Ford: realice exactamente k+1 pasadas de relajación, ya que k escalas equivalen a k+1 aristas. Utilice una copia de las distancias de la pasada anterior para asegurarse de no utilizar más saltos de los permitidos en una sola pasada; de lo contrario, una sola pasada podría encadenar varios saltos.
def findCheapestPrice_bf(n, flights, src, dst, k):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1): # k stops = k+1 edges
temp = dist[:] # copy to avoid using updated dist in same pass
for u, v, w in flights:
if dist[u] != float('inf') and dist[u] + w < temp[v]:
temp[v] = dist[u] + w
dist = temp
return dist[dst] if dist[dst] != float('inf') else -1
print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200SPFA: optimización basada en colas
Shortest Path Faster Algorithm (SPFA) es una versión optimizada de Bellman-Ford que solo vuelve a relajar las aristas que parten de nodos cuya distancia se acaba de actualizar, utilizando una cola. El caso medio es O(E), pero el peor caso sigue siendo O(V × E). SPFA rara vez es necesario en entrevistas, pero puede mencionarlo como optimización cuando Bellman-Ford es demasiado lento en grafos dispersos. Python no incluye un SPFA integrado, pero es sencillo implementarlo con collections.deque.
Detección de arbitraje de divisas
Una aplicación clásica de Bellman-Ford: dadas las tasas de cambio de divisas, determine si es posible realizar arbitraje (un ciclo en el que, al convertir divisas, se obtiene más de lo que se tenía inicialmente). Transforme las tasas tomando su logaritmo negativo. Arbitraje = un ciclo con peso logarítmico total negativo = un ciclo negativo que Bellman-Ford puede detectar. Esto permite trasladar problemas financieros del mundo real al algoritmo estándar.
import math
def has_arbitrage(rates):
n = len(rates)
# Transform: -log(rate) converts product to sum
log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
dist = [float('inf')] * n
dist[0] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return True # arbitrage!
return FalseOptimización mediante terminación anticipada
Si no se actualiza ninguna distancia en una pasada completa sobre todas las aristas, las pasadas posteriores tampoco actualizarán nada; termine antes. Esta optimización reduce la complejidad en el mejor caso a O(E) cuando el grafo ya es óptimo después de unas pocas pasadas. Añada una bandera updated = False al principio de cada pasada; si sigue siendo False después de la pasada, salga inmediatamente.
def bellman_ford_optimised(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # no more improvements possible
return distBellman-Ford en grafos con listas de adyacencia
Cuando el grafo se proporciona como una lista de adyacencia en lugar de una lista de aristas, conviértalo primero en una lista de aristas o recorra todas las entradas de la lista de adyacencia como aristas. Para V=1000 y E=5000, V-1=999 pasadas, recorriendo 5000 aristas en cada una, dan 4.995.000 operaciones, lo que está dentro de los límites de tiempo. Para grafos muy densos (E ≈ V²), el peor caso O(V³) coincide con el de Floyd-Warshall, por lo que la elección depende del contexto.
from collections import defaultdict
def bellman_ford_adj(V, adj, source):
# Convert adjacency list to edge list
edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return distComprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió que: Bellman-Ford relaja todas las aristas V-1 veces para gestionar aristas con pesos negativos, una pasada de relajación número V que todavía encuentra mejoras indica un ciclo negativo y el algoritmo es O(V × E), frente a O((V+E) log V) en Dijkstra. A continuación veremos Floyd-Warshall para encontrar los caminos más cortos entre todos los pares con un único cálculo O(V³).
Preguntas frecuentes
¿La lección «Bellman-Ford y ciclos negativos» es gratis?
Sí — el texto completo de «Bellman-Ford y ciclos negativos» 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 ciclos negativos»?
Realice n-1 pasadas de relajación sobre todas las aristas, detecte ciclos negativos con una pasada final y explique por qué Dijkstra falla con aristas de peso negativo. 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 2 de 4.
¿Cuánto tiempo toma la lección «Bellman-Ford y ciclos negativos»?
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
- Algoritmo de Dijkstra con una cola de prioridad
- Bellman-Ford y ciclos negativos
- Floyd-Warshall: caminos mínimos entre todos los pares
- Network Delay Time y reconstrucción de caminos