Les deux trouvent les chemins les plus courts à partir d'une source dans un graphe pondéré. Dijkstra est plus rapide mais nécessite des poids non-négatifs ; Bellman-Ford est plus lent mais gère les arêtes négatives et détecte les cycles négatifs.
Étendre répétitivement le nœud non visité le plus proche et relaxer ses voisins.
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
Relaxer toutes les arêtes V-1 fois ; une relaxation supplémentaire signifie un cycle négatif.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Poids | non-négatifs | quelconques (y compris négatifs) |
| Temps | O((V+E) log V) | O(V·E) |
| Cycle négatif | n/a | le détecte |
Utilisez Dijkstra par défaut pour les poids non-négatifs (cartes, réseaux). Utilisez Bellman-Ford quand des arêtes négatives existent (par exemple, arbitrage). Dijkstra s'arrête silencieusement sur les poids négatifs — un piège classique.
Les algorithmes de plus court chemin alimentent le routage, la navigation, les protocoles réseau et l'analyse des coûts de dépendance.
Connaître la contrainte de poids non-négatif sur Dijkstra prévient les mauvaises réponses sur le terrain.
L'idée de relaxation relie la pensée greedy et DP, ce qui en fait un sujet riche de niveau senior.