Quiz Graphes, plus cours chemins
Soit un graphe avec 5 sommets 0, 1, 2, 3, 4
Si 0->3->1->4->2 est un plus court chemin qui mène de 0 à 2 alors 0->3->1->4 n'est pas forcément le chemin le plus court de 0 à 4
Faux
C'est faux car s'il existe un chemin plus court pour mener de 0 à 4, 0->3->1->4->2 n'est pas le plus court chemin qui mène de 0 à 2.
Nous désirons trouver l'arbre des plus courts chemins dans un graphe acyclique en partant d'un sommet source. L'algorithme suivant est-il juste?
- Initialiser
distTo[v] = 0pour la source,distTo[v] = ∞pour les autres sommets - Traiter les sommets par ordre topologique
- Pour tous les arcs partant du sommet courant, relâcher l'arc
Vrai
Cet algorithme fonctionne pour les graphes acycliques
L'aglorithme de Dijkstra calcule l'arbre des plus courts chemins pour un graphe pondéré de poids non-négatifs.
Vrai
Soit un graphe acyclique avec 9 sommets.
Le résultat de son tri topologique est : 8, 7, 5, 1, 9, 4, 2, 3, 6
Effectuer l'aglorithme de calcul des plus courts chemins dans un graphe acyclique depuis le sommet 1
Donner comme réponse la liste des arrêtes faisant partie de l'arbre des plus courts chemins.
Les arcs sont à entrer par ordre croissant des sommets sous la forme suivante:
1-2,1-3,2-2,2-4,... où le sommet 1 a un arc le reliant au sommet 2, un autre au sommet 3, etc.
ATTENTION, il n'y a pas d'espace après les virgules
1-4,1-6,1-9,2-3,4-2
Soit un graphe avec 8 sommets
Effectuer l’algorithme de Dijkstra depuis le sommet 2
Réponder aux 3 questions suivantes en lien avec cet exercice.
1) Indiquer dans quelle ordre les sommets sont parcourus sous la forme 1,3,5,...
ATTENTION, il n'y a pas d'espace après les virgules
2,3,5,4,6,7,1
2) Indiquer les plus courtes distances pour chaque sommet sous la forme:
1/13,2/0,3/14... où la signification est <numéro sommet>/<distance minimale par rapport au sommet 2>.
Dans l'exemple le sommet 1 est à une distance de 13 du sommet 2, le sommet 2 à une distance 0 et le sommet 3 à une distance de 14.
ATTENTION, il n'y a pas d'espace après les virgules
1/13,2/0,3/7,4/10,5/8,6/11,7/13
3) Donner comme réponse la liste des arrêtes faisant partie de l'arbre des plus courts chemins.
Les arcs sont à entrer par ordre croissant des sommets sous la forme suivante:
1-2,1-3,2-2,2-4,... où le sommet 1 a un arc le reliant au sommet 2, un autre au sommet 3, etc.
ATTENTION, il n'y a pas d'espace après les virgules
2-3,2-4,3-5,3-6,4-7,6-1