Algorithme du plus court chemin

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 mêmes sommets. Mais aucune hypothèse sur le signe des poids n’est nécessaire.

On donnera une version qui repose sur un examen pré ordonné des sommets, mais elle ne s’applique qu’aux

graphes orientés sans circuits.

Définition 1. – Soit G = (S, A) un graphe orienté, sans circuits et I un sommet choisi comme

sommet initial. On appelle niveau du sommet S∈S, le nombre maximum d’arcs de tous les chemins

reliant I à S. Le niveau de I est 0.

Remarque : si un chemin reliant I à S contient un circuit, ce maximum n’existe pas, puisqu’à chaque tour de circuit,

on ajoute le nombre d’arcs dudit circuit.

Définition 2. – Un graphe dont les sommets ont été classés par niveau, est appelé graphe

ordonnancé. On dit aussi qu’on a partagé le graphe en niveaux.

Remarque : on « redessine » en général le graphe, en faisant apparaître les niveaux des sommets .

Voici donc l’algorithme de FORD, décomposé en trois phases :

Phase 1 :

- Affecter le poids 0 au sommet de niveau 0

Phase 2 :

- Pour chaque niveau et chaque sommet S de ce niveau, lui affecter le poids obtenu en prenant le minimum des

sommes Σ = {poids d’un des prédécesseurs de S + poids de l’arc reliant ce prédécesseur à S}

Phase 3 :

- Le chemin de poids minimum est l’un de ceux qui réalisent le poids du dernier sommet : il suffit donc d’une

lecture « à l’envers »

Remarques :

L’attribution des poids pour les sommets est définitive (ce qui réduit fortement le nombre d’opérations à

effectuer), grâce au partage préalable du graphe en niveaux ;

S’il y a plusieurs sommets de niveau 0, on applique l’algorithme à chacun des sommets de niveau 0 (sauf si l’on

recherche un chemin minimal de sommet initial bien précis), puis on compare les différents poids obtenus par

l’algorithme ;

Cet algorithme, en l’adaptant, permet aussi de trouver un chemin maximal

3-Algorithme de Bellman-Ford-Moore

Cet algorithme peut être vu comme une version améliorée de l'algorithme

proposé par Ford. Cette version est aussi appelée l'algorithme à correction

d'étiquette. Ci-dessous se trouve son pseudo-code:

1) Initialisation pour tout noeud

1. distance = infinie

2. père = NULL

2) Initialisation du noeud de départ

1. distance = 0

2. père = NULL

3) enfiler( L, noeud de départ )

4) Tant que a non NULL Faire

1. Noeud à traiter a = défiler(L)

2. Pour chaque noeud b relié à a Faire

a) distance d = distance de a + longueur de l'arc (a, b)

b) Si distance actuelle de b > d Alors

i. distance de b = d

ii. père de b = a

iii.enfiler( L, b )

c)