Cours 3

CHAPITRE II Problème du plus court chemin

Cours 3

Introduction :

Il est courant, lorsque l'on cherche à se rendre d'un point à un autre dans un réseau (routier, par exemple), de chercher le plus court chemin en anglais "shortest path", c'est-à-dire celui dont la distance est la plus petite. Si le nombre de trajets possibles entre le point de départ et le point d'arrivée est faible, il suffira de calculer les longueurs de chacun des trajets en additionnant la longueur des liens qui le composent et de comparer directement les longueurs obtenues. Mais une telle solution exhaustive devient rapidement impraticable si le nombre de trajets possibles est grand.

Heureusement, il existe des algorithmes qui évitent d'avoir à calculer tous les trajets possibles. Pour cela, ils mettent en œuvre diverses stratégies.

Plus court chemin

Dans un graphe valué, le poids c(p) d'un chemin p est la somme des poids des arêtes (arcs) le long du chemin. Dans ce qui suit nous appellerons le poids d'un chemin sa longueur. Le plus court chemin entre deux sommets s et t est alors défini comme le chemin de plus faible poids reliant s et t.

Remarque : Pour différencier la longueur d'un chemin telle que que nous l'avons définie pour un graphe

non valué, nous préciserons qu'il s'agit de la longueur en nombre d'arêtes. Cette confusion des deux définitions de la longueur se justifie par le fait que la longueur en nombre d'arêtes (arcs) correspond au poids d'une chaine (chemin) avec une valuation de 1 pour toutes les arêtes (arcs). Dans le graphe valué ci-contre, p = ( f, g, h, e, d, b ) a une longueur de 16. Il est le plus court chemin reliant les sommets f et b.

1.1 Objectif de l'algorithme de Dijkstra :Chercher dans un réseau (graphe) les plus courts chemins qui relient un sommet de départ s_deb à tous les autres sommets du graphe. L'agorithme de Dijkstra est basé sur le parcours des graphes en largeur.1.2 Description de l'algorithme de Dijkstra :Entrées : G=(S,A) un graphe avec une valuation positive v des arcs.

s_deb un sommet de S

Initialisation:

d[a]:= ∞ pour chaque sommet s ∈ S

d(s_deb)=0

P:=∅

Tant qu'il existe un sommet hors de P

Choisir un sommet a hors de P de plus petite distance d[a]

Mettre a dans P

Pour chaque sommet b hors de P voisin de a

d[b] = min (d[b] , d[a] + poids(a,b))

Fin Pour Fin Tant Que

1.3 Principe de l'algorithme de Dijkstra :

Le poids du chemin entre deux sommets est la somme des poids des arcs qui le composent. Pour une paire donnée de sommets s_deb (le sommet du départ) s_fin (sommet d'arrivée) appartenant à S, l'algorithme trouve le chemin depuis s_deb vers s_fin de moindre poids (autrement dit le chemin le plus léger ou encore le plus court).

L'algorithme fonctionne en construisant un sous-graphe P de manière à ce que la distance entre un sommet s de P depuis s_deb soit connue et soit un minimum dans G. Initialement P contient simplement le nœud s_deb isolé, et la distance de s_deb à lui-même vaut zéro. Des arcs sont ajoutés à P à chaque étape :

- En identifiant toutes les arêtes a_i = (s_i1,s_i2) dans G x P tel que s_i1 est dans P et s_i2 est dans G ;

- En choisissant l'arc a_j = (s_j1,s_j2) dans G x P qui donne la distance minimum depuis s_deb à s_j2 en passant tous les chemins créés menant à ce nœud.

L'algorithme se termine soit quand P devient un arbre couvrant de G, soit quand tous les nœuds d'intérêt sont dans P.

1.4 Exemple d'application :

Application de l'algorithme de Dijkstra pour déterminer le plus court chemin entre le sommet A et chacun des sommets de G.

1. Algorithme de Dijkstra :L'algorithme de Dijkstra calcule les plus courts chemins à partir d'une source dans un graphe pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre une source et un sommet d'arrivée. l'algorithme porte le nom de son inventeur, l'informaticien néerlandais Edsger Dijkstra, et a été publié en 1959.Edsger Wybe Dijkstra, né à Rotterdam le 11 mai 1930 et mort à Nuenen le 6 août 2002, est un mathématicien et informaticien néerlandais

1.5 Exercice supplémentaire :

1. En quoi consiste l'algorithme de Dijkstra ?

2. Appliquez l'algorithme de Dijkstra pour déterminer le plus court chemin entre le sommet s et chacun des sommets de G.

Page updated

Google Sites

Report abuse