Algorithme de Bellman-Ford
Les plus courts chemins depuis une source avec des poids quelconques : passes de relâchement de tous les arcs, tableau passe après passe, arrêt anticipé, détection d'un circuit de poids négatif, coût et lien avec le routage à vecteur de distances.
- 24 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Passe : de quoi s'agit-il ?
Voir la réponse
Tour complet de l'algorithme de Bellman-Ford, pendant lequel chaque arc du graphe est examiné une fois.
Après la passe k, la distance de tout sommet dont un plus court chemin compte au plus k arcs est exacte. C'est pourquoi n − 1 passes suffisent : un chemin simple a au plus n − 1 arcs.
Ce programme relâche les arcs dans l'ordre de la liste, pendant deux passes seulement. Qu'affiche-t-il ?
```python
arcs = [("C", "D", 2), ("B", "C", -3), ("A", "B", 5), ("S", "A", 4), ("S", "C", 10)]
dist = {v: float("inf") for v in "SABCD"}
dist["S"] = 0
for _ in range(2):
for u, v, w in arcs:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
print(dist)`{'S': 0, 'A': 4, 'B': 9, 'C': 10, 'D': 12}{'S': 0, 'A': 4, 'B': 9, 'C': 6, 'D': 8}{'S': 0, 'A': 4, 'B': inf, 'C': 10, 'D': inf}{'S': 0, 'A': 4, 'B': 9, 'C': 6, 'D': 12}
Voir la réponse
{'S': 0, 'A': 4, 'B': 9, 'C': 10, 'D': 12}À la passe 1, seuls A (4) et C (10) sont atteints, car les arcs sont examinés dans un ordre défavorable. À la passe 2, D = 12 (par C) puis B = 9 (par A). C ne tombe à 6 qu'à la passe 3 et D à 8 qu'à la passe 4 : il faut n − 1 = 4 passes.
Dans un graphe de n sommets sans circuit absorbant, … passes de relâchement de tous les arcs suffisent pour obtenir les plus courts chemins.
Voir la réponse
Dans un graphe de n sommets sans circuit absorbant, n − 1 passes de relâchement de tous les arcs suffisent pour obtenir les plus courts chemins.
Un plus court chemin simple traverse au plus n sommets, donc n − 1 arcs, et chaque passe en « finit » au moins un de plus.
Circuit absorbant : de quoi s'agit-il ?
Voir la réponse
Circuit dont la somme des poids est strictement négative : le parcourir en boucle fait baisser indéfiniment la longueur d'un chemin.
Si un tel circuit est accessible depuis la source, il n'existe pas de plus court chemin vers ses sommets : leur distance vaut moins l'infini.