Bellman-Ford et arêtes négatives
Gérer les valeurs négatives et détecter les cycles
Bellman-Ford et arêtes négatives est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 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 Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Quand Dijkstra échoue
Dijkstra considère qu'une distance retirée du tas est définitive, mais une arête négative peut ensuite rendre un chemin moins coûteux. L'algorithme échoue donc.
Voici Bellman-Ford
Bellman-Ford gère les poids d'arêtes négatifs. Il est plus lent que Dijkstra, mais fiable lorsque la logique gloutonne ne peut pas être utilisée en toute confiance.
L'opération principale
Il relâche à plusieurs reprises chaque arête : si dist[u] plus le poids de l'arête est inférieur à dist[v], mettez dist[v] à jour avec cette valeur plus petite.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wCombien de passages
Un plus court chemin utilise au plus V moins 1 arêtes. Ainsi, V-1 passages de relâchement de toutes les arêtes suffisent pour stabiliser toutes les distances.
for _ in range(n - 1):
relax_all_edges()Initialiser les distances
Commencez avec toutes les distances à l'infini, sauf celle de la source qui vaut zéro, exactement comme avec Dijkstra.
dist = [float('inf')] * n
dist[src] = 0Un passage complet
À chaque passage, parcourez toute la liste des arêtes une fois et relâchez chaque arête. Les améliorations se propagent d'un saut par passage.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wPourquoi V-1 suffit
Après k passages, tous les plus courts chemins utilisant k arêtes sont corrects. Après V-1 passages, chaque plus court chemin simple est terminé.
Le passage supplémentaire
Effectuez un passage de plus. Si une distance diminue encore, cela signifie que le coût continue de baisser, ce qui indique un cycle négatif.
Détecter les cycles négatifs
Un cycle négatif signifie qu'aucun plus court chemin fini n'existe, car vous pouvez le parcourir indéfiniment pour réduire le coût sans limite.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'Le temps d'exécution
Vous relâchez E arêtes pendant V passages : Bellman-Ford s'exécute donc en O(V * E), ce qui convient aux graphes petits ou moyens.
Dijkstra ou Bellman-Ford
Choisissez Dijkstra pour les poids non négatifs et la rapidité. Choisissez Bellman-Ford en présence de valeurs négatives ou si vous devez détecter un cycle problématique.
Vérification rapide
Après V-1 passages, une distance diminue encore lors d'un passage supplémentaire. Qu'est-ce que cela signifie ?
Récapitulatif : Bellman-Ford
Relâchez toutes les arêtes pendant V-1 passages, puis effectuez-en un autre pour détecter les cycles négatifs. L'algorithme s'exécute en O(V*E), mais fonctionne là où Dijkstra échoue. ✅
Questions Fréquemment Posées
La leçon « Bellman-Ford et arêtes négatives » est-elle gratuite ?
Oui — le texte complet de « Bellman-Ford et arêtes négatives » 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 Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Bellman-Ford et arêtes négatives » ?
Gérer les valeurs négatives et détecter les cycles Tu pratiques Competitive Programming Academy 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 Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy 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 3 sur 4.
Combien de temps prend la leçon « Bellman-Ford et arêtes négatives » ?
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 Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy 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
- Dijkstra avec un tas
- BFS 0-1 avec une deque
- Bellman-Ford et arêtes négatives
- Floyd-Warshall entre toutes les paires