GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:graphes:dijkstra

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
nsi:terminales:graphes:dijkstra [2021/11/08 19:40] – ↷ Page déplacée de nsi:terminales:dijkstra à nsi:terminales:graphes:dijkstra goupillwikinsi:terminales:graphes:dijkstra [2021/11/12 16:41] (Version actuelle) – goupillwiki
Ligne 3: Ligne 3:
 Pour les besoins de cette partie, considérons un réseau constitué de routeurs, sur lequel on indique les distances entre routeurs. Pour les besoins de cette partie, considérons un réseau constitué de routeurs, sur lequel on indique les distances entre routeurs.
  
-{{ :nsi:terminales:graphe_reseau_1.svg |}}+{{ :nsi:terminales:graphes:graphe_reseau_1.svg |}}
  
 On souhaite trouver le plus court chemin entre deux sommets. On souhaite trouver le plus court chemin entre deux sommets.
Ligne 20: Ligne 20:
 Sélection du sommet de départ R1. On lui affecte une pondération de 0 puisque la distance |R1,R1| est 0. Tous les autres sont affectés pour l'instant d'une distance ∞. Sélection du sommet de départ R1. On lui affecte une pondération de 0 puisque la distance |R1,R1| est 0. Tous les autres sont affectés pour l'instant d'une distance ∞.
  
-{{ :nsi:terminales:graphe_dijkstra_1.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_1.svg |}}
  
 ==== Étape 2 ==== ==== Étape 2 ====
Ligne 28: Ligne 28:
 En empruntant l'arête R1 - R2, cela fait une distance |R1,R2| de 4, ce qui est mieux que ∞. On sélectionne donc l'arête R1 - R2 (en orange) et on indique que R2 est pour l'instant, au mieux, à une distance de 4 depuis R1. On fait de même pour les autres voisins de R1, c'est à dire R3 et R4. En empruntant l'arête R1 - R2, cela fait une distance |R1,R2| de 4, ce qui est mieux que ∞. On sélectionne donc l'arête R1 - R2 (en orange) et on indique que R2 est pour l'instant, au mieux, à une distance de 4 depuis R1. On fait de même pour les autres voisins de R1, c'est à dire R3 et R4.
  
-{{ :nsi:terminales:graphe_dijkstra_2.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_2.svg |}}
  
 ==== Étape 3 ==== ==== Étape 3 ====
Ligne 34: Ligne 34:
 Parmi tous les non pris, R3 est le plus proche de R1. On le sélectionne donc. On avait mis en surbrillance l'arête R1 - R3 ce qui indiquait que le meilleur chemin pour atteindre R3 était l'arête R1 - R3. Ceci ne changera plus, cet arête est définitivement validée. Parmi tous les non pris, R3 est le plus proche de R1. On le sélectionne donc. On avait mis en surbrillance l'arête R1 - R3 ce qui indiquait que le meilleur chemin pour atteindre R3 était l'arête R1 - R3. Ceci ne changera plus, cet arête est définitivement validée.
  
-{{ :nsi:terminales:graphe_dijkstra_3.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_3.svg |}}
  
 ==== Étape 4 ==== ==== Étape 4 ====
Ligne 40: Ligne 40:
 R3 étant le dernier pris, on examine ses voisins non pris, R4 et R5. Puisque |R1,R3| = 1 et que R3 - R4 est pondéré 1, cela ferait, en passant par R3, |R1,R4| = 2 ce qui est mieux que le |R1,R4| = 3 antérieur. On change donc le poids de R4 en le mettant à 2. Il vaut donc mieux arriver à R4 depuis R3. On désélectionne l'arête R1 - R4 (grisée) et on sélectionne l'arête R3 - R4. Pas de commentaire sur R5. R3 étant le dernier pris, on examine ses voisins non pris, R4 et R5. Puisque |R1,R3| = 1 et que R3 - R4 est pondéré 1, cela ferait, en passant par R3, |R1,R4| = 2 ce qui est mieux que le |R1,R4| = 3 antérieur. On change donc le poids de R4 en le mettant à 2. Il vaut donc mieux arriver à R4 depuis R3. On désélectionne l'arête R1 - R4 (grisée) et on sélectionne l'arête R3 - R4. Pas de commentaire sur R5.
  
-{{ :nsi:terminales:graphe_dijkstra_4.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_4.svg |}}
  
 ==== Étape 5 ==== ==== Étape 5 ====
Ligne 46: Ligne 46:
 Le meilleur sommet est maintenant R4. On le place parmi les pris. On sait aussi maintenant que la meilleure arête pour atteindre R4 sera R3 - R4 (en vert) et que cela ne changera plus. Le meilleur sommet est maintenant R4. On le place parmi les pris. On sait aussi maintenant que la meilleure arête pour atteindre R4 sera R3 - R4 (en vert) et que cela ne changera plus.
  
-{{ :nsi:terminales:graphe_dijkstra_5.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_5.svg |}}
  
 ==== Étape 6 ==== ==== Étape 6 ====
Ligne 52: Ligne 52:
 Examen des voisins non pris de R4. Pas de commentaires pour R6 et R7. Si on voulait atteindre R2 en passant par R4, cela donnerait |R1,R2| = 7 ce qui est moins bien que |R1,R2| = 4 que l'on avait déjà. L'arête R4 - R2 peut donc être abandonnée (grisée). Examen des voisins non pris de R4. Pas de commentaires pour R6 et R7. Si on voulait atteindre R2 en passant par R4, cela donnerait |R1,R2| = 7 ce qui est moins bien que |R1,R2| = 4 que l'on avait déjà. L'arête R4 - R2 peut donc être abandonnée (grisée).
  
-{{ :nsi:terminales:graphe_dijkstra_6.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_6.svg |}}
  
 ==== Étape 7 ==== ==== Étape 7 ====
Ligne 58: Ligne 58:
 Le meilleur sommet suivant est R2... Le meilleur sommet suivant est R2...
  
-{{ :nsi:terminales:graphe_dijkstra_7.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_7.svg |}}
  
 ==== Étape 8 ==== ==== Étape 8 ====
Ligne 64: Ligne 64:
 Le dernier voisin de R2 a envisager est R7, mais l'arête R2 - R7 n'améliore pas le chemin déjà connu jusque R7. On abandonne donc l'arête R2 - R7. Le dernier voisin de R2 a envisager est R7, mais l'arête R2 - R7 n'améliore pas le chemin déjà connu jusque R7. On abandonne donc l'arête R2 - R7.
  
-{{ :nsi:terminales:graphe_dijkstra_8.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_8.svg |}}
  
 ==== Étape 9 ==== ==== Étape 9 ====
Ligne 70: Ligne 70:
 Sélection de R6... Sélection de R6...
  
-{{ :nsi:terminales:graphe_dijkstra_9.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_9.svg |}}
  
 ==== Étape 10 ==== ==== Étape 10 ====
Ligne 76: Ligne 76:
 Le passage par R6 n'améliore pas le parcours jusque R5 (R6 - R5 grisé) mais améliore le chemin jusque R7 (désélection de R4 - R7 et sélection de R6 - R7) Le passage par R6 n'améliore pas le parcours jusque R5 (R6 - R5 grisé) mais améliore le chemin jusque R7 (désélection de R4 - R7 et sélection de R6 - R7)
  
-{{ :nsi:terminales:graphe_dijkstra_10.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_10.svg |}}
  
 ==== Étape 11 ==== ==== Étape 11 ====
Ligne 82: Ligne 82:
 Sélection de R5 qui n'a plus de voisins à examiner. Sélection de R5 qui n'a plus de voisins à examiner.
  
-{{ :nsi:terminales:graphe_dijkstra_11.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_11.svg |}}
  
 ==== Étape 12 ==== ==== Étape 12 ====
Ligne 88: Ligne 88:
 Sélection de R7 qui n'a lus de voisins à examiner. Sélection de R7 qui n'a lus de voisins à examiner.
  
-{{ :nsi:terminales:graphe_dijkstra_12.svg |}}+{{ :nsi:terminales:graphes:graphe_dijkstra_12.svg |}}
  
 À la fin de cet algorithme, on sait à la fois la plus courte distance menant d'un certain sommet (ici R1) jusque tous les autres, et aussi les chemins permettant de réaliser ces plus courtes distances. À la fin de cet algorithme, on sait à la fois la plus courte distance menant d'un certain sommet (ici R1) jusque tous les autres, et aussi les chemins permettant de réaliser ces plus courtes distances.
Ligne 97: Ligne 97:
 Faites le même travail, à partir de R1, avec le graphe suivant : Faites le même travail, à partir de R1, avec le graphe suivant :
  
-{{ :nsi:terminales:graphe_reseau_2.svg |}}+{{ :nsi:terminales:graphes:graphe_reseau_2.svg |}}
 </WRAP> </WRAP>
  
Ligne 105: Ligne 105:
 ==== À faire ==== ==== À faire ====
  
-Écrivez en pseudo-code une version de l'algorithme de Dijkstra. +  * Écrivez en pseudo-code une version de l'algorithme de Dijkstra.\\ Vous pourrez utiliser des fonctions comme //ajouter sommet à la liste des pris//, ou //extraire le sommet de plus petit poids parmi les non pris// ou //successeurs de sommet//... 
- +  * Implémentez une fonction dijkstra dans la classe ''WGraph'' créée précédemment.
-Vous pourrez utiliser des fonctions comme //ajouter sommet à la liste des pris//, ou //extraire le sommet de plus petit poids parmi les non pris// ou //successeurs de sommet//... +
-</WRAP> +
- +
-==== Graphe pondéré ==== +
- +
-Vous disposez déjà d'une classe pour graphe orienté. +
- +
-Modifier cette classe pour permettre l'ajout d'une pondération. +
- +
-<WRAP tip> //Remarque un peu technique// +
- +
-On définit une classe pour un graphe non pondéré. On souhaite ajouter des pondérations. Certaines caractéristiques du graphe ne dépendent pas de la pondération et ne devraient donc pas être modifiées. Par exemple les relations de voisinage, la liste des sommets, la matrice d'adjacence... L'ajout de la pondération ne devrait donc pas modifier le fonctionnement de ces aspects inchangés du graphe. +
- +
-D'une façon générale, il faut songer que l'utilisateur de la classe n'accède qu'aux attributs et méthodes publics de la classe. Il faut s'assurer que la modification apportée à la classe maintienne le fonctionnement de ces attributs et méthodes de sorte que la modification ne gêne pas les programmes qui utilisaient l'ancienne version de la classe. +
-</WRAP>  +
- +
-<WRAP tip>=== Notion d'héritage === +
- +
-Les classes proposent un mécanisme appelé héritage. Supposons que j'ai créé une classe appelée ''Graph'' qui décrivent un graphe non pondéré. Je veux créer une classe ''WGraph'' pour un graphe pondéré. Cette nouvelle classe est largement identique à l'ancienne. On n'a pas envie de tout réécrire. On a envie de dire que ''WGraph'' reprend tout le contenu de ''Graph'' à quelques exceptions près. Eh bien on peut le faire : +
- +
-<code python> +
-from graph import Graph +
- +
-class WGraph(Graph): +
-    # WGraph récupère tout le contenu de Graph +
-    # on peut préciser des modifications ou des ajouts +
-</code> +
-</WRAP> +
- +
-<WRAP box>=== À faire === +
- +
-  * Implémentez la classe ''WGraph''. +
-  * Implémentez l'algorithme de Dijkstra+
 </WRAP> </WRAP>
nsi/terminales/graphes/dijkstra.1636396802.txt.gz · Dernière modification : de goupillwiki