Ambos encuentran caminos más cortos desde una fuente en un grafo ponderado. Dijkstra es más rápido pero requiere pesos no negativos; Bellman-Ford es más lento pero maneja aristas negativas y detecta ciclos negativos.
Expande repetidamente el nodo no visitado más cercano y relaja sus vecinos.
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq) # closest first
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # relax edge
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
Relaja todas las aristas V-1 veces; una relajación adicional significa un ciclo negativo.
| | Dijkstra | Bellman-Ford | |---|---------|| | Pesos | no negativos | cualquiera (incl. negativos) | | Tiempo | O((V+E) log V) | O(V·E) | | Ciclo neg. | n/a | lo detecta |
Usa Dijkstra por defecto para pesos no negativos (mapas, redes). Usa Bellman-Ford cuando existen aristas negativas (p. ej., arbitraje). Dijkstra falla silenciosamente con pesos negativos — una trampa clásica.
Los algoritmos de camino más corto impulsan el enrutamiento, navegación, protocolos de red y análisis de costos de dependencias.
Conocer la restricción de peso no negativo en Dijkstra previene respuestas incorrectas en la práctica.
La idea de relajación conecta el pensamiento greedy y DP, lo que la convierte en un tema rico de nivel senior.