Ceci est une ancienne révision du document !
Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 172
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Constant SVG_DPI already defined in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 75
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined array key "inResponsiveUnits" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 282
Warning: Undefined array key "hasCssClasses" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 301
Warning: Undefined array key "print" in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 322
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Table des matières
Plus court chemin, Algorithme de Dijkstra
Pour les besoins de cette partie, considérons un réseau constitué de routeurs, sur lequel on indique les distances entre routeurs.
On souhaite trouver le plus court chemin entre deux sommets.
Algorithme de Dijkstra
Détaillons le déroulement de l'algorithme de Dijkstra en partant du sommet R1.
Je noterai par exemple |R1,R3| une distance d'un chemin de R1 à R3. Cette distance dépend du chemin pris et on cherche la plus petite valeur possible.
Dans l'algorithme, on associe progressivement chaque sommet à une valeur, un poids, qui représente la meilleure distance trouvée jusque là depuis le sommet de départ. Par exemple, si on écrit (R4,3), cela veut dire qu'à ce moment de l'exécution, la meilleure distance |R1,R4| est 3. Mais cela pourra changer.
Étape 1
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 ∞.
Étape 2
Examen de tous les voisins non pris du dernier sommet pris (ici R1)
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.
Étape 3
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.
Étape 4
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.
Étape 5
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.
Étape 6
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).
Étape 7
Le meilleur sommet suivant est R2…
Étape 8
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.
Étape 9
Sélection de R6…
Étape 10
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)
Étape 11
Sélection de R5 qui n'a plus de voisins à examiner.
Étape 12
Sélection de R7 qui n'a lus de voisins à examiner.
À 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.
À faire
Faites le même travail, à partir de R1, avec le graphe suivant :
Implémentation
À faire
É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…
Graphe pondéré
Vous disposez déjà d'une classe pour graphe orienté.
Modifier cette classe pour permettre l'ajout d'une pondération.
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.
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 :
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
À faire
- Implémentez la classe
WGraph. - Implémentez l'algorithme de Dijkstra