Bellman-Ford et cycles négatifs
Effectuez n-1 passes de relaxation sur toutes les arêtes, détectez les cycles négatifs lors d’une dernière passe et expliquez pourquoi Dijkstra échoue avec des arêtes de poids négatif.
Bellman-Ford et cycles négatifs est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Pourquoi Bellman-Ford existe
Bellman-Ford résout le problème du plus court chemin depuis une source unique, comme Dijkstra, mais il gère les poids d'arêtes négatifs. Il détecte également les cycles négatifs — des cycles dont le poids total est négatif, ce qui rend impossible la définition d'un plus court chemin fini qui les traverse. Bien qu'il soit plus lent que Dijkstra, Bellman-Ford est le bon choix dès que le graphe peut contenir des arêtes de poids négatif.
La relaxation : l'opération essentielle
Bellman-Ford repose sur une seule opération : la relaxation. Relaxer l'arête (u, v, w) signifie : si dist[u] + w < dist[v], mettre à jour dist[v] = dist[u] + w. Nous relaxons toutes les arêtes de manière répétée. L'idée essentielle est la suivante : tout plus court chemin comporte au plus V-1 arêtes (dans un graphe sans cycles négatifs). Par conséquent, V-1 passes de relaxation sur toutes les arêtes suffisent pour trouver tous les plus courts chemins.
Implémentation de Bellman-Ford
Représentez le graphe sous forme de liste d'arêtes [(u, v, weight)]. Initialisez dist[source] = 0 et toutes les autres distances à inf. Effectuez V-1 passes, en relaxant toutes les arêtes à chaque passe. Toute mise à jour qui se produit encore lors de la Vᵉ passe indique un cycle négatif.
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]Pourquoi V-1 passes suffisent
Dans un graphe sans cycles négatifs, un plus court chemin visite chaque nœud au plus une fois ; il comporte donc au plus V-1 arêtes. Après la première passe, les plus courts chemins comportant 1 saut sont optimaux. Après la deuxième passe, ceux comportant 2 sauts sont optimaux. Après V-1 passes, tous les plus courts chemins (qui utilisent au plus V-1 sauts) ont été trouvés. Si une distance est encore mise à jour lors de la passe V, le graphe contient un cycle négatif accessible depuis la source.
Détection des cycles négatifs
Après V-1 passes, effectuez une passe supplémentaire sur toutes les arêtes. Si une arête (u, v, w) vérifie dist[u] + w < dist[v], alors un cycle négatif existe et le plus court chemin vers certains nœuds vaut -infinity. Les applications concrètes comprennent la détection de possibilités d'arbitrage dans les échanges de devises (cycles négatifs dans les graphes pondérés par des logarithmes) et la détection d'incohérences dans les systèmes de contraintes.
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)) # TrueComparaison entre Dijkstra et Bellman-Ford
Dijkstra : O((V+E) log V), nécessite des poids non négatifs, approche gloutonne. Bellman-Ford : O(V × E), gère les poids négatifs et détecte les cycles négatifs. Pour la plupart des problèmes d'entretien avec des poids non négatifs, Dijkstra est préférable. Lorsque des poids négatifs apparaissent (par exemple, « trouver le plus court chemin avec des arêtes de coût négatif » ou « détecter un arbitrage »), Bellman-Ford est la solution. Pour les graphes denses, le pire cas O(V³) de Bellman-Ford est comparable à celui de Floyd-Warshall.
Application : vols les moins chers avec Bellman-Ford
Le problème des vols les moins chers avec K escales (LeetCode 787) peut être résolu avec une version modifiée de Bellman-Ford : effectuez exactement k+1 passes de relaxation (car k escales signifient k+1 arêtes). Utilisez une copie des distances de la passe précédente afin de ne pas utiliser plus de sauts que permis en une seule passe — sinon une seule passe pourrait enchaîner plusieurs sauts.
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 : optimisation fondée sur une file
Algorithme d'accélération des plus courts chemins (SPFA) est une version optimisée de Bellman-Ford qui ne réapplique la relaxation qu'aux arêtes partant des nœuds dont la distance vient d'être mise à jour, en utilisant une file. Le coût moyen est O(E), mais le pire cas reste O(V × E). SPFA est rarement nécessaire lors des entretiens, mais vous pouvez le mentionner comme optimisation lorsque Bellman-Ford est trop lent sur les graphes creux. Python ne fournit pas de SPFA intégré, mais son implémentation avec collections.deque est simple.
Détection de l'arbitrage de devises
Une application classique de Bellman-Ford : étant donné des taux de change, détecter si un arbitrage est possible (un cycle dans lequel la conversion des devises rapporte plus que la somme de départ). Effectuez une transformation en prenant le logarithme négatif des taux de change. Un arbitrage équivaut à un cycle dont le poids logarithmique total est négatif, c'est-à-dire à un cycle négatif détectable par Bellman-Ford. Cela permet de modéliser des problèmes financiers réels avec l'algorithme standard.
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 FalseOptimisation par arrêt anticipé
Si aucune distance n'est mise à jour lors d'une passe complète sur toutes les arêtes, les passes suivantes ne modifieront rien non plus : arrêtez-vous immédiatement. Cette optimisation réduit la complexité dans le meilleur cas à O(E) lorsque le graphe est déjà optimal après quelques passes. Ajoutez un indicateur updated = False au début de chaque passe ; s'il reste à False après la passe, interrompez immédiatement l'algorithme.
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 sur des graphes avec listes d'adjacence
Lorsque le graphe est fourni sous forme de liste d'adjacence plutôt que de liste d'arêtes, convertissez d'abord cette liste en liste d'arêtes, ou parcourez toutes les entrées de la liste d'adjacence comme des arêtes. Pour V=1000 et E=5000, V-1=999 passes parcourant chacune 5000 arêtes donnent 4,995,000 opérations — ce qui reste largement dans les limites de temps. Pour les graphes très denses (E ≈ V²), le pire cas O(V³) correspond à celui de Floyd-Warshall, ce qui rend le choix dépendant du contexte.
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 distVérification rapide
Vérifiez votre compréhension des concepts de Structures de données et algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que Bellman-Ford relaxe toutes les arêtes V-1 fois pour gérer les arêtes de poids négatif, qu'une Vᵉ passe de relaxation qui trouve encore des améliorations indique un cycle négatif, et que l'algorithme est en O(V × E), contre O((V+E) log V) pour Dijkstra. Ensuite, nous étudierons Floyd-Warshall pour trouver les plus courts chemins entre toutes les paires de nœuds en un seul calcul en O(V³).
Questions Fréquemment Posées
La leçon « Bellman-Ford et cycles négatifs » est-elle gratuite ?
Oui — le texte complet de « Bellman-Ford et cycles négatifs » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Bellman-Ford et cycles négatifs » ?
Effectuez n-1 passes de relaxation sur toutes les arêtes, détectez les cycles négatifs lors d’une dernière passe et expliquez pourquoi Dijkstra échoue avec des arêtes de poids négatif. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Bellman-Ford et cycles négatifs » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Algorithme de Dijkstra avec file de priorité
- Bellman-Ford et cycles négatifs
- Floyd-Warshall : plus courts chemins entre toutes les paires
- Délai du réseau et reconstruction du chemin