Algorithme du point fixe de Ford-Bellman
Problématique du problème de cheminement
Il calcule les plus courts chemins d'un point x donné à tous les points du graphe en utilisant une technique de marquage.
En fin de calcul, on peut obtenir la description du plus court chemin de x à n'importe quel point y donné
Convergence
L'algorithme converge si le graphe ne comporte pas de circuit de longueur strictement négative.
Il converge donc sans problème si on suppose que toutes les valeurs des arcs sont des nombres entiers positifs.
Technique utilisée
On utilise une procédure de marquage.
Au départ, les marques sont égales à +∞
(c'est à dire que l'on considère qu'il n'existe pas de plus court chemin de x à tous les autres points,
+∞ est l'élément neutre de l'opérateur min).
On balaie l'ensemble des arcs jusqu'à ce qu'il n'y ait plus de modification de marques entre deux itérations successives.
Chaque fois que l'on trouve un arc (u,z) qui complète un chemin issu de x,, on regarde si ce nouveau chemin est plus court que les chemins déjà trouvés qui arrivent en z et si c'est le cas, on diminue la marque de z et on retient que l'on est venu de u pour arriver en z par ce chemin plus court.
Structures de données
La matrice V donne la longueur des arcs du graphe.
V(i,j) est égale à +≈ quand l'arc (i,j) n'existe pas.
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 β contient, par exemple, -1.
Description de l'algorithme de calcul des plus courts chemins
Initialisation
Pour tout i faire
π(i)=+∞ ;
β(i)=-1 ;
Fin pour i ;
π(x)=0 ;
modif=vrai ;
Itérations
Tant que modif = vrai faire
modif=faux ;
Pour tout i de 1 à n faire
Pour tout j de 1 à n faire
Si π(i)+V(i,j)<π(j) alors
π(j)=π(i)+V(i,j) ;
β(j)=i ;
modif= vrai ;
Fsi
Fin Pour tout j ;
Fin Pour tout i :
Fin Tanque
Éléments de preuve
Elle se fait par récurrence.
A l'itération 0, les marques donnent la longueur du plus court chemin élémentaire d'au plus 0 arcs entre le point x et les autres points.
Si on suppose qu'à l'itération p-1, les marques donnent la longueur du plus court chemin élémentaire d'au plus p-1 arcs entre le point x et les autres points, alors à l'intération p, les marques donnent bien la longueur du plus court chemin d'au plus p arcs entre le point x et les autres points.
Comme un chemin élémentaire comporte au plus n-1 arcs, on est certain que l'algorithme converge.
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
Déroulement de l'algorithme du point fixe sur des graphes
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 β.
Cliquez de manière itérée sur le bouton ARCS pour balayer les arcs. Le numéro d'itération change chaque fois que l'on recommence le balayage au premier arc. L'indicateur de modification est rose et "faux" chaque fois que l'on commence une itération et devient bleu et "vrai" à la première modification trouvée.
Si l'indicateur reste rose et "faux" à la fin d'une itération, on vous demande 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.
Complexité de l'algorithme
Il y a au plus n-1 itérations (longueur du plus long chemin élémentaire).
A l'intérieur de chaque itération il y a au plus m arcs à examiner, à condition que le graphe soit représenté par la liste de ces arcs.
L'algorithme est donc en O(n.m).
Modification de l'algorithme pour obtenir des chemins maximaux
L'algorithme converge si le graphe ne comporte pas de circuit de longueur strictement positive.
Si les valeurs sont toutes des entiers positifs, il faut donc que le graphe ne comporte pas de circuit, par contre, il peut contenir des cycles.
Il suffit de passer de MIN à MAX, d'où le changement de l'élément neutre à l'initialisation et l'inversion du test dans les itérations.
Changement pour l'initialisation
π(i)=-∞ ;
Changement pour les itérations
Si π(i)+V(i,j)<π(j) alors
Modification de l'algorithme pour obtenir l'existence de chemins de x à tout point i
L'algorithme converge toujours car on change au plus une fois la marque des points en la faisant passer de "faux" à "vrai".
Les valeurs dans la matrice sont égales à vrai lorsque l'arc existe et à faux sinon.
Il suffit de passer de MIN à OU logique.
Changement pour l'initialisation
π(i)=faux ; pour tout i
π(x)=vrai ;
Changement pour les itérations
Si (π(i) et V(i,j) = vrai) et π(j) = faux alors
π(j)=vrai ;
β(j)=i ;
modif= vrai ;
Fsi
