Méthodes de Recherches de Chemins PDF

Méthodes de recherches de chemins 1  Méthodes de recherches de chemins 2  Méthodes de recherches de chemins 3  Méthodes de recherches de chemins 4  Méthodes de recherches de chemins 5  Méthodes de recherches de chemins Problème du plus court chemin 6  Méthodes d...

Méthodes de recherches de chemins 1  Méthodes de recherches de chemins 2  Méthodes de recherches de chemins 3  Méthodes de recherches de chemins 4  Méthodes de recherches de chemins 5  Méthodes de recherches de chemins Problème du plus court chemin 6  Méthodes de recherches de chemins Problème du plus court chemin 7  Méthodes de recherches de chemins 8  Méthodes de recherches de chemins Exemple 9  Algorithme de Dantzig (pour des longueur positives l(u)> 0)  Considérons sur le graphe, le sommet de départ a = a1, le sommet d’arrivée b = am, et déterminons pour tout sommet x un nombre t(x) qui sera la valeur du plus court chemin entre a et x.  On opère par étape :  On pose t(a1)= 0 ;  Supposons qu’à la k ème étape, on ait défini la fonction sur un ensemble Ak = a1, a2, …, ak, on associera à chaque sommet aj  Ak un sommet bj  AK / arc (aj, bj) existe et tel que la longueur l( aj, bj ) soit minimale, puis on chercheras le sommet aq  Ak / t(aq) + l(aq + bq) soit égale au min  t(aj) + l(aj + bj)  On pose Ak+1 = Ak  bk  t(bq) = t(aq) + l(aq + bq) 10  Algorithme de Ford Recherche du plus court d’un sommet à tous les autres dans un graphe quelconque représenté par -  Soit un graphe G(X, - )  Poser  (1) = 0 et  (i) =  pour les autres sommets i.  Pour i = 2 à N faire  (i)  min ( (j) + lij )  Recommencer à 2 jusqu’à ce que les  (i) se stabilisent. 11