Université Paris Dauphine Algorithmes dans les graphes
Licence Informatique des Organisations - 3ème année 2022-2023
TP noté
Durée : 1h30
Soit le graphe G valué suivant :
8
0 2 1 4 5
2 6
3 6 −1 1
3 11 2
−3
1 −1
3 1 5
−6
7
15
10
1. Déterminer un plus court chemin allant de 0 à 7 dans G à l’aide de l’algorithme de général. Pour
cela, vous ferez appel à la fonction algoGeneral() disponible dans la section TPnote sur moodle
dans le fichier [Link]. Ce fichier contient également une description de G sous la forme d’une
liste d’arcs. Les arguments de la fonction algoGeneral() sont un graphe G de type DiGraph de
networkx et un sommet i0. Cette fonction détermine les plus courts chemins issus de i0 en appliquant
l’algorithme général de Ford-Bellman et renvoie une liste de listes : la sous-liste k contient les marques
(λk (i), pk (i)) obtenues à l’itération k. Afficher la valeur du plus court chemin allant de 0 à 7 dans G
ainsi que le nombre d’arcs nbA qu’il contient.
2. Afficher les plus courts chemins allant de 0 à 7 et leur valeur (lorsqu’ils existent) :
- comportant au plus nbA arcs,
- comportant au plus nbA-1 arcs,
- ...
- comportant au plus 2 arcs,
- comportant au plus 1 arcs.
Indication : Après avoir appliqué l’algorithme général, on dispose des marques (λk (i), pk (i)) pour tout
i et pour tout k allant de 1 à nbA. Pour déterminer un plus court chemin allant de 0 à 7 comportant au
plus t arcs, on récupère le prédécesseur du sommet 7 contenu dans pt (7) et noté s, puis on récupère le
prédécesseur de s contenu dans pt−1 (s)... jusqu’à atteindre le sommet 0.
3. Un arc est dit vital si sa suppression entraîne une augmentation de la longueur du plus court chemin
allant de i0 à j0. Ecrire une fonction appelée detVital() qui prend en argument un graphe G,
un sommet origine i0, un sommet destination j0, un plus court chemin µ∗ allant de i0 à j0 et sa
valeur v(µ∗ ). Cette fonction renvoie la liste des arcs vitaux. Pour savoir si un arc (i, j) de µ∗ est vital,
il suffit de le supprimer de G avant de calculer la valeur v d’un plus court chemin allant de i0 à j0 : si
v > v(µ∗ ) l’arc (i, j) est vital.
4. Afficher à l’écran une représentation graphique de G (aussi proche que possible de celle de l’énoncé)
en coloriant en rouge les arcs vitaux pour aller de 0 à 7.
1
5. Un arc vital est maximal si sa suppression engendre la plus grande augmentation de la longueur du plus
court chemin allant de i0 à j0. Afficher l’arc vital maximal pour aller de 0 à 7 dans G.
6. Proposer une variante de la fonction algoGeneral() permettant de trouver tous les plus courts
chemins partant de i0. Représenter graphiquement l’ensemble des plus courts chemins allant de 0 à 7.
7. Déposer votre programme (nommé votreNom_votrePré[Link]) sous moodle dans la section TPnoté.
