On considère dans cet exercice des graphes pondérés.
Si un graphe n'est pas orienté, on considère le graphe obtenu en remplaçant chaque arête par deux arcs d'orientations opposées avec les mêmes extrémités.
Un graphe est représenté par les listes de successeurs à l'aide d'un dictionnaire :
les clés sont les sommets du graphe et pour chaque clé \(s\), la valeur associée est la
liste des couples \((u, p)\) où \(u\) est un successeur du sommet \(s\) et \(p\) est le poids de l'arc \((s, u)\).
Par exemple, avec les deux graphes dessinés ci-dessous, le graphe orienté à gauche est représenté par le dictionnaire {"A":[("B",5),("C",4)],"B":[("C",3),("D",3),("E",2)],"C":[("B",-2),("D",2)],"D":[("C",3),("E",-2)],"E":[]}
et le graphe orienté (non connexe) à droite, par le dictionnaire {"A":[("B",3),("C",6)],"B":[("A",3),("C",2),("D",5)],"C":[("A",6),("B",2),("D",4)],"D":[("B",5),("C",4)],"E":[]}.
Un chemin est une suite d'arcs \((s_0, s_1), (s_1, s_2), (s_2, s_3), ..., (s_{q-1}, s_q)\). Un circuit est un chemin tel que \(s_0 = s_q\).
Le poids d'un chemin est la somme des poids des arcs constituant le chemin. Certains arcs peuvent avoir des poids négatifs
mais on suppose pour les questions 1, 2, 3 que le graphe ne contient pas de circuit dont le poids total est négatif.
La distance entre deux sommets \(u\) et \(v\) est le poids minimal d'un chemin allant de \(u\) à \(v\). S'il n'existe pas de chemin entre deux sommets, la distance entre ces deux sommets est infinie.
Le problème posé est : déterminer les distances entre un sommet source et chaque sommet du graphe.
1. Programmation dynamique
Pour résoudre le problème posé, on va résoudre tous les problèmes : déterminer les distances entre un sommet source et chaque sommet du graphe en utilisant au plus \(i\) arcs,
\(i\) allant de \(0\) à \(n-1\) où \(n\) est l'ordre du graphe.
Si \(S\) est le sommet source et \(u\) un sommet quelconque, on note \(d(u, i)\) la distance entre \(S\) et \(u\) en utilisant au plus \(i\) arcs. On a alors les relations :
\(d(S, 0) = 0\);
\(d(u, 0) = \infty\) si \(u\neq S\);
pour \(i\) allant de \(1\) à \(n-1\), \(d(u, i) = min(d(u, i-1), d(v, i-1) + p(v, u))\) où \(p(v, u)\) est le poids de l'arc \((v, u)\).
En effet, pour atteindre \(u\) avec au plus \(i\) arcs, on peut atteindre \(u\) avec au plus \(i-1\) arcs ou, s'il existe un arc \((v, u)\), atteindre \(v\) avec au plus \(i-1\) arcs et terminer le chemin par l'arc \((v, u)\).
La solution au problème initial est alors donnée pour tout sommet \(u\) par \(d(u, n-1)\).
Compléter la fonction distances_1 ci-dessous, qui prend en paramètres un dictionnaire représentant un graphe et un sommet source, et construit un dictionnaire dist dont les clés sont les couples
de la forme \((s, i)\) avec pour valeur associée \(d(s, i)\), pour tout \(s\) sommet du graphe et tout \(i\) entier allant de \(0\) à \(n-1\). Le dictionnaire dist est renvoyé à la fin.
Une double boucle permet de parcourir les arcs : parcours des sommets puis, pour chaque sommet, parcours de la liste de successeurs.
Pour représenter \(\infty\), une variable inf a été définie par inf=float("inf"). Elle est directement utilisable dans le code de la fonction.
Dans cette question, on reprend la fonction distances_1 de la question précédente et on la modifie pour obtenir la fonction distance_2.
Principe de la modification: pour évaluer la valeur associée à une clé \((s, i)\), \(i >0\), on n'utilise que les valeurs associées aux clés de la forme \((s, i-1)\).
Il n'est donc pas nécessaire de garder en mémoire toutes les clés (au nombre de \(n^2\) en fin de boucle, avec \(n\) sommets et \(n\) valeurs possibles pour \(i\)).
À chaque passage dans la boucle externe, on dispose d'un dictionnaire dist, dont les clés sont les sommets \(s\), correspondant
à l'utilisation d'au plus \(i-1\) arcs, on construit, lors du parcours des arcs à l'aide des deux boucles internes, un dictionnaire dist2, dont les clés sont les sommets \(s\), mais correspondant à l'utilisation d'au plus \(i\) arcs,
puis on remplace dist par dist2 avant le passage suivant dans la boucle externe. On n'utilise ainsi plus que \(2\times n\) clés, \(n\) pour chacun des deux dictionnaires. C'est une économie importante sur le coût en mémoire.
Compléter la fonction distances_2.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Dans cette question on procède à une nouvelle modification: on ne crée plus un nouveau dictionnaire dist2, mais on modifie le dictionnaire initial dist.
Dans ce cas, on obtient pour chaque valeur de i, une valeur pour dist[s2] qui est inférieure ou égale à \(d(s2, i)\). Donc la procédure est "accélérée".
La variable i ne représente plus le nombre maximal d'arcs utilisés, mais simplement le nombre de passages dans la boucle externe.
Compléter la fonction bellman_ford_1. Cette fonction implémente l'algorithme de Bellman-Ford.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Cette question traite de deux améliorations possibles de la fonction bellman_ford_1.
Les distances cherchées peuvent être obtenues en moins de \(n-1\) passages dans la boucle. Dans ce cas il est possible d'interrompre le programme.
Pour cela, on ajoute une variable modif initialisée à False avant l'examen des arcs (les deux boucles internes). Si lors d'un examen une distance est modifiée, la valeur de la variable modif
devient True. Si cette variable n'a pas été modifiée après un examen des arcs, alors on interrompt la boucle externe, sinon on continue.
Si le graphe contient un circuit dont le poids total est négatif, alors un examen supplémentaire des arcs va entraîner une diminution de la valeur pour certaines distances.
On ajoute donc un nouvel examen des arcs, après la boucle externe, pour tester s'il y a une modification d'une distance. Si c'est le cas, le graphe contient un cycle de poids total négatif.
Compléter la fonction bellman_ford_2 avec les deux modifications proposées. Cette fonction doit renvoyer un triplet constitué du dictionnaire des distances dist,
du nombre de passages effectivement réalisés dans la boucle externe et de la valeur True ou False selon que le graphe contient un cycle négatif ou pas.
Remarque importante
Après la fin d'une boucle foriinrange(a,b), la variable i reste accessible et a pour valeur b-1. Par exemple:
>>> foriinrange(1,7): pass>>> i6
Dans d'autres langages, la variable déclarée dans la boucle est limitée à la boucle. On dit qu'elle est dans la portée du bloc for et elle n'est pas visible en dehors.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)