Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithme controle IUT Info GI Ann ?ee - P ?eriode et Cours sur les graphes petit contr ole Florent Madelaine Nom Corrig ?e Pr ?enom L ? algorithme de Bellman-Ford On rappelle l ? algorithme vu en cours ci-contre a- Expliquer comment faire pour stocker l

IUT Info GI Ann ?ee - P ?eriode et Cours sur les graphes petit contr ole Florent Madelaine Nom Corrig ?e Pr ?enom L ? algorithme de Bellman-Ford On rappelle l ? algorithme vu en cours ci-contre a- Expliquer comment faire pour stocker les plus courts chemins calcul ?es On m ?emorise pour chaque sommet son pr ?ed ?ecesseur sur un chemin depuis la source s Ainsi achaque fois qu ? on rel ache un arc u v cela signi ?e que le chemin de sa v passe dor ?enavant par u autrement dit le pr ?ed ?ecesseur de v est maintenant le sommet u On peut par exemple stocker ces pr ?ed ?ecesseurs dans un tableaux index ?e par les sommets du graphe b- Am ?eliorer le pseudo-code ci- contre pour mettre en place ce stockage des plus courts chemins c- Donner un exemple de graphe orient ?e valu ?e pour lequel il y a un chemin entre deux sommets s et t mais il n ? y a pas de plus court chemin de s a t On peut consid ?erer par exemple un graphe pour lequel il y a un chemin non- ?el ?ementaire entre les deux sommets s et t chemin qui a donc un circuit qu ? on choisira en plus de poids total n ?egatif par exemple ?? Algorithme Bellman-Ford ? ??Donn ?ees G un graphe orie ? ??nt ?e valu ?e sans circuit de longueur strictement n ?egative s un sommet de G Variables locales L tableau des distances depuis s indexe ? par les sommets P red tableau des pr ?ed ?ecesseurs sur un plus court chemin depuis s u v un arc d ?ebut initialisation L s pour tous les sommet v s faire L v ? tant que L change faire relaxation de l ? arc u v ? ?? pour chaque arc u v de G faire ?? ? si L v L u length u v G alors ?? ? L v L u length u v G Pred v u ?nsi ?nprch ?ntq ?n Sorties L le tableau des distances des plus court chemins de s P red le tableau des pr ?ed ?ecesseurs sur un plus court chemin depuis s CLes Algorithmes Cours sur les graphes d- En plus de calculer des plus courts chemins d ? une source a tous les autres sommets dans un graphe sans circuit de poids n ?egatif quelle autre fonction peut remplir l ? algorithme de Belman-Ford dans un graphe quelconque On peut d ?ecider si le graphe a un circuit de poids n ?egatif En e ?et on a vu en cours que l ? algorithme e ?ectue au plus n- it ?erations de la boucle Tant Que dans un graphe sans circuit n ?egatif Donc pour un graphe quelconque il su ?t de faire une nieme it ?eration et de v ?eri ?er si oui ou non lors de cette ultime it ?eration le tableau L a chang