Question de code
Vérifier si il y a du code à la toute fin de l’exercice.
Analyse d’algorithmes 1 boucle
- Poser soit K le nombre d’intégrations
- Expliciter la condition de fin
- Déterminer la plus petite valeur de K vérifiant la condition d’arrêt
- Conclure
Implémentation de List : Généralement lorsqu’on écrit begin() et end() ne pas oublier qu’on veut retourner des …
ITERATOR (à la place des nodes directement).
Prouver que belman-ford renvoi vrai seulement s’il n’y a pas de cycle de longueur négative
1- Définir un cycle < v0, v1, .., vk >
2- Poser la condition qui retourne vrai :
dv1 <= dv0 + w(v0, v1)
3 - Donc dv1 + dv2 + .. dvk <= dv0+dv1+..+dvk-1 + w(v0,v1) + w(v1,v2)+..+w(vk-1, vk)
4 - On simplifie par dv1+..+dvk-1 qui sont de chaque bord.
dv0 <= dvk + w(v0,v1) + w(v1,v2)+..+w(vk-1, vk)
5- Énoncer dv0 = dvk car c’est un cycle
6- Donc
0 <= w(v0,v1) + w(v1,v2)+..+w(vk-1, vk)
7- donc la longueur du cycle doit être >= 0 CQFD.
Prouver que Belman-Ford va renvoyer le plus court chemin
- Poser un plus court chemin v0,v1,.., vk
- Pas de cycle de longueur négative donc |S|-1 arcs au plus par chemin.
- Tous les arcs de S sont relâchés à chaque |S| - 1 itérations
- (v0,v1) sera relâché à l’itération 1
- (vi-1,vi) sera relâché à l’itération i
- Donc tous les arcs du plus court chemin de v0 à vk seront relâchés dans l’ordre au court des |S|-1 itérations nonobstant les relâchements intermédiaires.
- Cela vérifie la propriété des relâchementss des plus court chemin donc dvk = D(v0, vk) = le plus court chemin de v0 à vk.
