Ambos encontram caminhos mais curtos a partir de uma fonte em um grafo ponderado. Dijkstra é mais rápido, mas requer pesos não-negativos; Bellman-Ford é mais lento, mas lida com arestas negativas e detecta ciclos negativos.
Expanda repetidamente o nó não visitado mais próximo e relaxe seus vizinhos.
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
Relaxe todas as arestas V-1 vezes; relaxação adicional significa um ciclo negativo.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Pesos | não-negativos | qualquer (incluindo negativo) |
| Tempo | O((V+E) log V) | O(V·E) |
| Ciclo neg. | n/a | detecta |
Use Dijkstra por padrão para pesos não-negativos (mapas, redes). Use Bellman-Ford quando arestas negativas existem (ex: arbitragem). Dijkstra falha silenciosamente com pesos negativos — uma armadilha clássica.
Algoritmos de caminho mais curto alimentam roteamento, navegação, protocolos de rede e análise de custo de dependência.
Conhecer a restrição de peso não-negativo em Dijkstra evita respostas erradas na prática.
A ideia de relaxação conecta pensamento guloso e DP, tornando um tópico rico em nível sênior.