Algorithme de Bellman-Ford
Plus courts chemins avec poids négatifs
Enonce
Implémenter Bellman-Ford. Tester avec un graphe contenant des poids négatifs. Détecter un cycle de poids négatif.
Signature attendue
def bellman_ford(sommets: list, aretes: list, source: int) -> dict:Exemple
bellman_ford([0, 1, 2], [(0, 1, 4), (1, 2, -2), (0, 2, 5)], 0)→{0: 0, 1: 4, 2: 2}
📖 Rappel de cours
L'algorithme de Bellman-Ford calcule les plus courts chemins depuis une source, même avec des poids négatifs. Il détecte aussi les cycles de poids négatif.
Principe :
Relaxer toutes les arêtes $|V|-1$ fois. Si une $|V|$-ième passe améliore encore, il y a un cycle négatif.
Complexité :
$O(|V| \cdot |E|)$
Plus lent que Dijkstra, mais fonctionne avec des poids négatifs.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Composantes Connexes
- Détection de Cycle dans un Graphe Non Orienté
- Tri Topologique
- Algorithme de Prim
- Algorithme de Kruskal
- Coloration de Graphe
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.