Algorithme Du Plus Court Chemin

Dissertations gratuites, mémoires, discours et notes de recherche

Dissertations

Voir la version complète Algorithme Du Plus Court Chemin

Algorithme Du Plus Court Chemin

Imprimer Document!

S'inscrire - Rechercher de 155.000+ Dissertations

Catégorie: Société

Soumis par: Bruce 30 novembre 2011

Mots: 3648 | Pages: 15

...

de rapidité, cet algorithme ne permet que la recherche des chemins

de longueur minimale et pour des graphes pondérés par des poids positifs.

Donnons cet algorithme, autorisant la recherche d’un chemin minimal entre deux sommets I

(initial) et F (final). Il se décompose en quatre phases, comme suit :

Phase 1 : mise en place

- On désigne par Σ l’ensemble dans lequel on met les sommets au fur et à mesure de leur

marquage définitif ;

- A chaque sommet S, on associe le couple (dist(S), p(S)) où dist(S) désigne la distance

(provisoire ou définitive) de I à S, et p(S) le prédécesseur de S ;

Phase 2 : initialisation

- Attribuer au sommet I, le couple (0, I) ;

- Attribuer à chaque sommet adjacent à I, le couple (poids de l’arc le reliant à I, I) ;

- Attribuer aux autres sommets, le couple (+ ∞, ?) ;

Phase 3 : fonctionnement

Tant que tous les sommets ne sont pas dans Σ, ou que le sommet F n’est pas affecté de la plus

petite distance provisoire :

- Choisir parmi les sommets non placés dans Σ, un dont la distance provisoire est minimale :

appelons-le S ;

- Mettre S dans Σ ;

- Pour chacun des sommets i Y qui lui sont adjacents et qui ne sont pas dans Σ :

• Calculer s = dist(S) + poids de l’arc [S, i Y ] ;

• Si s est inférieur à la distance provisoire de i Y , attribuer à i Y le couple (s, S);

(ainsi, dist( i Y ) := min{dist(S) + poids de l’arc [S, i Y ] , dist( i Y )})

Phase 4 : conclusion

- La longueur du plus court chemin de I à F est alors dist(F) ;

- La chaîne de poids minimum se lit « à l’envers », de F à chacun de ses prédécesseurs

successifs.

Le principe est donc le suivant : on affecte provisoirement le poids maximal (+ ∞) à tous les

sommets, sauf pour le sommet initial de poids 0 et ses successeurs (recevant le poids de l’arc les

reliant à I) ; tant que c’est possible, on diminue les poids provisoires qui deviennent définitifs (un

sommet affecté d’un poids définitif est dit marqué) lorsque leur diminution devient impossible.

Remarque : il se peut que l’algorithme se termine avant que tous les sommets ne soient marqués

(cf. l’alternative du début de la phase 3) ; cela voudra dire qu’aucun des chemins passant par ces

sommets non marqués ne sera un chemin de longueur minimale.

Inconvénients:

Cet algorithme comme celui de Bellman-Ford-Moore est de type glouton.

C'est pourquoi dans un certain nombre de cas où les cases à traiter ont un même

niveau de trafic l'algorithme n'est pas très performant car il les parcourt toutes. C'est

pareil si nous prenons un autre critère de tri comme la distance entre la case à traiter

et la case d'arrivée. Nous verrons plus loin comment on peut guider cet algorithme

dans la recherche afin d'éviter de parcourir toutes les cases inutilement

Puisque chaque noeud traité est marqué, nous ne pouvons pas revenir en

arrière. De ce fait, l'algorithme de Dijkstra est inadapté quand nous avons des arcs de

poids négatif. Dans ce genre de situation, l'algorithme doit pouvoir revenir en arrière

pour modifier les étiquettes. C'est le cas de l'algorithme Bellman-Ford-Moore.

Avantages:

Avec cet algorithme, nous pouvons nous arrêter dès que le point d'arrivé

devient la case à traiter puisque le chemin que nous avons construit jusque là est un

chemin minimal.

Le système de marque empêche l'algorithme de revenir en arrière. Il améliore

ainsi sa performance

2-Algorithme de FORD

Un des premiers algorithmes est dû au mathématicien FORD : son peu d’efficacité découle du fait qu’on liste

les sommets intermédiaires dans un ordre quelconque : on risque donc de se retrouver un grand nombre de fois

avec les

...