Algorithme de chemins extrémaux utilisant une pile
Problématique du problème de cheminement
Il calcule les plus courts chemins d'un point x donné à tous les points (accessibles) du graphe en utilisant une technique de marquage ainsi qu'une structure de données de type pile de manière à visiter de manière organisée les descendants du point x.
En fin de calcul, on peut obtenir la description du plus court chemin de x à n'importe quel point y donné si chaque fois que l'on améliore la marque d'un point, on retient le prédécesseur immédiat qui apporte cette amélioration.
Convergence
L'algorithme converge toujours car on contrôle les fermetures de circuits.
Définition : fonctionnement d'une pile
Une pile est une structure de données telle que l'objet visible au sommet de la pile est toujours le dernier objet empilé, qui est également le premier objet qui sera dépilé.
La pile correspond à la politique dernier arrivé, premier servi.
Dans l'algorithme qui va suivre, on note :
sommet(Pile) : la valeur du dernier objet ("visible") qui a été mis sur la structure de donnée appelée Pile.
empiler(Pile, y) : l'opération qui consiste à ajouter l'objet y au sommet de la structure de données appelée Pile.
dépiler(Pile) ou dépiler(Pile, y) : l'opération qui consiste à supprimer le dernier objet qui a été empilé. Le paramètre y est facultatif, puisqu'il est inutile de désigner l'objet qui est au sommet et qui va disparaître de la pile sauf si l'on veut effectuer une vérification.
Structure de données utilisées
La matrice V donne la longueur des arcs du graphe.
V(i,j) est égale à +∞ quand l'arc (i,j) n'existe pas.
Outre une pile, on utilise trois tableaux :
Le tableau π contient la longueur (calculée progressivement) des plus courts chemins de x à tout point i.
Initialement, π(i) =0 si i=x et +∞ sinon.
Le tableau β contient le point qui précède un point donné dans le plus court chemin déjà trouvé issu de x.
Initialement β(i) = -1, par exemple , -1 ne correspondant à aucun numéro de point.
Le tableau dp contient la valeur "vrai" pour les points qui sont dans la pile et la valeur "faux" pour les points qui ne sont pas dans la pile.
Hypothèse
On suppose que les successeurs d'un point sont visités dans l'ordre croissant de leurs numéros.
Technique utilisée
On construit sur une pile les chemins qui partent de x et qui atteignent tous ses descendants.
Chaque fois que l'on atteint un descendant, on améliore si possible la longueur du plus court chemin de x à ce point.
On met le descendant sur la pile s'il n'y est pas déjà (cela évite de boucler sur les circuits).
Description de l'algorithme de calcul des plus courts chemins au moyen d'une pile
Initialisation
Pour tout i faire
π(i)=+∞ ;
β(i)=-1 ;
dp(i)="faux" ;
Fin pour i ;
Pile = ∅ ;
empiler(Pile,x) ;
π(x)=0 ;
dp(x)="vrai" ;
indz=-1 ;
Itérations
Tant que Pile ≠ ∅faire
i = sommet(Pile) ;
j = plus petit numéro de successeur de i > indz ou -1 si ce successeur n'existe pas.
Si j ≥ 0 et dp(j)="faux" alors
On regarde si ce nouveau chemin de x à j qui n'est pas déjà dans la pile améliore le meilleur chemin trouvé
Si π(i)+V(i,j)<π(j) alors
π(j)=π(i)+V(i,j) ;
β(j)=i ;
empiler(Pile,j) ;
dp(j)="vrai" ;
indz=-1 ;
Fsi
Sinon
On a examiné tous les successeurs du sommet de la pile i
On change z pour que le point i ne puisse pas être repris comme successeur du nouveau sommet
dépiler(Pile) ;
dp(i)="faux" ;
z=i ;
Fsi
Fin Tanque
Définition : Recherche d'un plus court chemin de x à un point y
La technique est exactement la même que pour l'algorithme du point fixe.
Description de l'algorithme permettant de trouver le plus court chemin de x à y donné
On obtient les points dans l'ordre inverse du chemin
k=0 ;
num(k)=y ;
u=β(y) ;
tantque u >0 faire
k=k+1 ;
num(k)=u ;
u=β(u) ;
finttantque
Cliquez sur Anim pour démarrer l'animation. Choisissez un graphe avec les boutons précédent et suivant. Il est à noter que changer de graphes réinitialise l'algorithme.
Vous devez ensuite choisir une valeur pour le point x origine des chemins, et valider.
Cliquez sur DEB_IT pour initialiser les tableaux π et β, ainsi que la pile avec le point x choisi.
Cliquez de manière itérée sur le bouton SUITE pour examiner les successeurs non encore considérés du sommet de la pile. Si le successeur de numéro supérieur au dernier numéro considéré pour le sommet de la pile existe, comme pour l'algorithme de point fixe, on regarde si on peut améliorer le plus court chemin de x à ce successeur et on corrige en conséquence les tableaux π et β. Si le successeur est déjà sur la pile, il existe au moins un circuit dans le graphe et il ne faut pas remettre ce point sinon l'algorithme bouclerait. Dans le cas contraire on empile le successeur. Lorsque le sommet n'a plus de successeurs non examiné, on le dépile. Lorsque la pile est vide, les calculs de plus courts chemins du point x vers tous les points est terminé.
On vous demande alors de choisir un point z afin de mettre en évidence en rouge sur la représentation graphique le plus court chemin de x à z (il apparaît en partant du point z et en remontant le chemin).
On vous signale les cas particuliers : chemin vide de x à x, inexistence du chemin et dans tous les cas, on vous propose, soit de changer la valeur de z, soit de changer la valeur de z ou celle de x.
Un des exemples proposés contient un circuit de manière à vous montrer comment l'algorithme se comporte en présence d'un circuit.
