Algorithme De Dijkstra

Algorithme de Dijkstra

L’algorithme de Dijkstra, contrairement à celui de Bellman, s’applique aux graphes dont les valuations

sont positives. En revanche, le graphe peut comporter des circuits.

C’est également un algorithme glouton : à chaque étape un nouveau sommet i sera marqué (les

valeurs λ(i) et π(i) seront alors définitives), puis on utilisera la technique de relâchement afin d’améliorer

les chemins menant aux successeurs de i.

Ce nouveau sommet marqué sera choisi comme celui dont la valeur du chemin depuis x0 est minimale

parmi tous les sommets non encore marqués. En effet, on est alors assuré que les résultats pour ce sommet

ne pourront être améliorés car

– les chemins passant par des sommets déjà tous marqués ont été pris en compte dans la valeur

actuelle de λ(i),

– un chemin passant par un sommet non encore marqué sera nécessairement de poids supérieur

puisqu’on a choisi i tel que λ(i) est minimal et que les valuations des arcs sont positives.

Algorithme 6 Algorithme de Dijkstra (plus courts chemins, valuations positives)

Dijkstra(G, x0)

1: Initialisation(G, x0)

2: E ← ∅ [E est l’ensemble des sommets marqués]

3: tantque E 6= S faire

4: i ← un sommet non marqué tel que λ(i) est minimal

5: marquer le sommet i

6: pour tout j ∈ Γ

+(i) faire

7: si j n’est pas marqué alors

8: Relâcher(G, i, j)

9: finsi

10: fin pour

11: E ← E ∪ {i}

12: fin tantque

Algorithme de Bellman

Cet algorithme s’applique aux graphes sans circuit et pour la recherche des plus courts chemins d’un

sommet sans prédécesseur x0 vers tous les autres sommets. La première étape consistera à renuméroter

les sommets de façon à ne jamais “revenir sur nos pas”, c’est le rôle de l’algorithme de tri topologique

d’un graphe.

3.4.1 Tri topologique d’un graphe sans circuit

Soit G un graphe à n sommets sans circuit, G possède alors au moins un sommet sans prédécesseur

que l’on note x0. L’algorithme suivant permet d’effectuer un tri topologique du graphe, c’est-à-dire une

renumérotation des sommets d’un graphe orienté de telle sorte que :

...