[PDF] Algorithmes de recherche du plus court chemin

View - Download Algorithmes de recherche du plus court chemin

Previous PDF

Next PDF

THEG24colange@epita.lrde.frIIAlgorithmes de recherche du plus court chemin

THEG25colange@epita.lrde.frMotivation

Beaucoup de problèmes de la vie quotidienne

peuvent être représentés sous forme de graphes... Le calcul de distance (et donc un plus court chemin) en est un des plus courants : Les logiciels de GPS calculant des itinéraires routiers

Distribution de chaleur dans les alentours

Connexion à haut débit par câble

Routage dans des réseaux de télécommunications THEG26colange@epita.lrde.frQuelques définitions AB FECD HG4 242
-3 237
-31

48Définitions :La longueur d'un chemin est la somme des poids des arcsLa distance entre x et y (noté, d(x,y)) est le minimum des

longueurs sur tous les chemins. Un plus court chemin entre x et y est un chemin dont la longueur est égale à d(x,y).

Exemples : Longueur de (A,E,F,B) est

4 + 2 + (-3) = 3 d(A, B) = 3 Plus court chemin entre A et B :

(A, E, F, B)

THEG27colange@epita.lrde.frRemarques

Etant donnés deux sommets x et y, plusieurs cas se présentent :

1) il n'y a pas de chemin de x à y.

2) il existe un ou plusieurs plus courts chemins de x à y.

3) il existe des chemins de x à y mais pas de plus court.

AB FECD HG4 241
-2 217
-31 -4-2Exemples :

1) il y a pas de chemins entre A et H

(donc, pas de plus court chemin)

2) il existe deux plus courts chemins

entre A et B : (A,B) et (A,E,F,B)

3) il existe une infinité de plus courts

chemins entre B et F : (B,C,F), (B,C,F,B,C,F)....

4) Il existe des chemins entre D et G mais pas de plus court : les chemins

(D,H,G,D,H,G....) sont arbitrairement courts.

THEG28colange@epita.lrde.frCircuit absorbant

Définition :

Un circuit absorbant est un circuit de longueur négative. Si un graphe possède un circuit absorbant, alors il n'existe pas de plus court chemin entre certains de ses sommets. Théorème : Soit G un graphe orienté pondéré n'ayant pas de circuits absorbants, et x et y deux sommets de G. Si il existe un chemin allant de x à y, alors la distance d(x,y) est bien définie et il existe au moins un plus court chemin d e x à y. Attention : sauf indication contraire, les graphes que nous allons traiter par la suite sont sans circuit absorbant. THEG29colange@epita.lrde.frPropriétés des plus courts chemins Propriété 1 : Tout sous-chemin d'un plus court chemin est un plus court chemin. Propriété 2 : Si il existe un plus court chemin entre deux sommets x et y, alors il existe un plus court chemin élémentaire (sans cycle) entre x et y. THEG30colange@epita.lrde.frCalcul de distance : cas d'un graphe pondéré à 1 C'est un cas particulier de calcul de distance, dans le cas où tous les

arcs sont de poids 1. Étant donné un sommet initial x, on cherche à déterminer d(x,y) pour

tout sommet y.

Principe :

Un sommet y est à distance n de x si :

il existe un chemin de longueur n de x à y, il n'existe pas de chemin de longueur strictement inférieure à n de x à y.

Ces deux conditions peuvent se réécrire :

y est le successeur d'un sommet à distance n - 1 de x. La distance de x à y n'est pas plus petite que n. THEG31colange@epita.lrde.fr Calcul de distance : algorithme

Distance (graphe G, sommet s)

POUR CHAQUE

v ≠ s FAIRE couleur(v)  Blanc ; distance(v)  ∞ couleur( s)  Rouge distance( s)  0

F  {s}

TANT-QUE not (FileVide(

F)) FAIRE

s  Défiler(F )

POUR CHAQUE

v  δ(s)SI couleur( v) = Blanc ALORS couleur( v)  Rouge distance( v)  distance(s) + 1 père( v)  s

Enfiler(

F,v)

FIN SI

FIN POUR

couleur( s)  Noir FIN-TANT-QUECalculer la complexité dans les deux cas :

1) liste d'adjacence ;

2) matrice d'adjacence

THEG32colange@epita.lrde.fr Calcul de distance : liste d'adj.

Distance (graphe G, sommet s)

POUR CHAQUE

v ≠ s FAIRE couleur(v)  Blanc ; distance(v)  ∞ couleur( s)  Rouge distance( s)  0

F  {s}

TANT-QUE not(FileVide(

F)) FAIRE

s  Défiler(F )

POUR CHAQUE

v  δ(s)SI couleur( v) = Blanc ALORS couleur( v)  Rouge distance( v)  distance(s) + 1 père( v)  s

Enfiler(

F,v)

FIN SI

FIN POUR

couleur( s)  Noir

FIN-TANT-QUEO(|S|)

O(1)

O(|S|)

O(|S|)

O(|A|)O(|A|)

O(|A|)

O(|S|)

O(|S| + |A|)

THEG33colange@epita.lrde.frCalcul de distance : matrice d'adj.

Distance (graphe G, sommet s)

POUR CHAQUE

v ≠ s FAIRE couleur(v)  Blanc ; distance(v)  ∞ couleur( s)  Rouge distance( s)  0

F  {s}

TANT-QUE not(FileVide(

F)) FAIRE

s  Défiler(F )

POUR CHAQUE

v  δ(s)SI couleur( v) = Blanc ALORS couleur( v)  Rouge distance( v)  distance(s) + 1 père( v)  s

Enfiler(

F,v)

FIN SI

FIN POUR

couleur( s)  Noir

FIN-TANT-QUEO(|S|)

O(1)

O(|S|)

O(|S|)

O(|S|2)O(|A|)

O(|A|)

O(|S|)

O(|S|2 + |A|)

THEG34colange@epita.lrde.frExemple calcul de distance

A l'état initial :

seul le sommet A est rouge

La file est réduite au site A

AB FECD dA(H)=∞dA(G)=∞dA(F)=∞dA(E)=∞AFile F THEG35colange@epita.lrde.frExemple calcul de distance

On défile le sommet A

On visite les voisins blancs de A : B et E

Le sommet A devient noir

B FECD

HGdA(A)=0dA(B)=1dA(B)=∞dA(D)=∞

dA(H)=∞dA(G)=∞dA(F)=∞dA(E)=1File FBBEA THEG36colange@epita.lrde.frExemple du BFS et le calcul de distance

On défile le sommet B

On visite le voisin blanc de B : C

Le sommet B devient noir

B FECD

HGdA(A)=0dA(B)=1dA(B)=2dA(D)=∞

dA(H)=∞dA(G)=∞dA(F)=∞dA(E)=1File FA BCBE THEG37colange@epita.lrde.frExemple calcul de distance

On défile le sommet E

On visite le voisin blanc de B : F

Le sommet B devient noir

dA(A)=0dA(B)=1dA(B)=1dA(D)=∞ dA(H)=∞dA(G)=∞dA(F)=1dA(E)=1File FA BFBC EB FC GD H THEG38colange@epita.lrde.frExemple calcul de distance

On défile le sommet F

F n'a pas de voisin blanc

Le sommet F devient noir

dA(A)=0dA(B)=1dA(B)=1dA(D)=∞ dA(H)=∞dA(G)=3dA(F)=1dA(E)=1File FA BG EB FC GD H THEG39colange@epita.lrde.frExemple calcul de distance

On défile le sommet G

G n'a pas de voisin blanc

Le sommet G devient noir

dA(A)=0dA(B)=1dA(B)=1dA(D)=∞ dA(H)=∞dA(G)=1dA(F)=1dA(E)=1File FA EB FCD

HG: VIDE

THEG40colange@epita.lrde.frExemple calcul de distance Il n'y a plus de sommet à défiler : Fin de l'algorithme

On obtient une arborescence en largeurv  S, dA(v) = longueur du plus court chemin entre A et vdA(A)=0dA(B)=1dA(B)=2dA(D)=∞

dA(H)=∞dA(G)=3dA(F)=1dA(E)=1File FA EB FCD

HG: VIDE

THEG41colange@epita.lrde.frExemple calcul de distance dA(A)=0dA(B)=1dA(B)=1dA(D)=∞ dA(H)=∞dA(G)=1dA(F)=1dA(E)=1A EB FCD

HGATTENTION :

Dans un parcours en largeur : tous les sommets ne sont pas visités Ainsi les sommet inaccessibles depuis l'origine gardent une distance ∞

Sommets

inaccessibles depuis le sommet A THEG42colange@epita.lrde.frPrincipes des algorithmes dans le cas général (1/2) Étant donnés un graphe pondéré et un sommet s, on veut déterminer pour chaque sommet x la distance et un plus court chemin (par rapport à s). Les algorithmes de recherche de distance et de plus court chemin dans un graphe pondéré fonctionnent de la façon suivante. On calcule les distances d(s,x) par approximations successives. À un stade donné de l'algorithme on dispose d'estimations, distance(s), (éventuellement égales à +∞) pour ces distances, et de la donnée d'un prédécesseur Père(s) pour les plus courts chemins. THEG43colange@epita.lrde.frPrincipes des algorithmes dans le cas général (2/2) s xydistance(y) p(x,y)distance(x) A chaque étape, on essaye d'améliorer les valeurs obtenues précédemment : on considère un sommet x et un successeur y de x. On compare la valeur distance(y) a celle que l'on obtiendrait en passant par x, i.e., distance(x)+p(x,y). Si cette deuxième valeur est plus petite que distance(s), on remplace l'estimation distance(y) par distance(x)+p(x,y) et le père de y par x. Cette technique est appelée la technique de relaxation. La question est : comment appliquer la relaxation de façon efficace ? THEG44colange@epita.lrde.frCalcul de distance dans un graphe pondéré positif :

Algorithme de Dijkstra (principe)

Met en oeuvre le principe général en le traduisant par la propriété suivante:Considérons un ensemble E de sommets (incluant la source s), dont on a calculé la distance

par rapport à s. Pour tout sommet x en dehors de E, nous déifinissons sa distance partielle (estimée) à s par :

distance(s, x) = min{ d(s, y) + p(y, x) | y ∈ E } (par convention : p(y,x) = +∞ si (y, x) ∉ A.)

Alors, si z est un sommet avec la plus petite distance partielle, sa distance partielle est

égale à sa distance à s :

distance(s, z) = d(s, z) La distance partielle correspond à la longueur du plus court chemin de s à x qui n'emprunte que des sommets de E (à l'exception bien sûr du dernier sommet x). C'est donc le plus court chemin dans le sous-graphe induit par E ∪ {x}. THEG45colange@epita.lrde.frCalcul de distance dans un graphe pondéré positif :

Algorithme de Dijkstra (principe)

Met en oeuvre le principe général en traduisant par la propriété suivante: On construit petit à petit, à partir de {s}, un ensemble E de sommets marqués. Pour tout sommet marqué x, l'estimation d(x) est

égale à la distance d(s, x).

À chaque étape, on sélectionne un sommet non marqué x dont la distance estimée d(x) est la plus petite parmi tous les sommets non marqués. • On marque alors x (on rajoute x à E), puis on met à jour à partir de x les distances estimées des successeurs non marqués de x. • On recommence, jusqu'à épuisement des sommets non marqués. THEG46colange@epita.lrde.frCalcul de distance dans un graphe pondéré positif :

Algorithme de Dijkstra

Distance-pondere-pos (graphe G=, sommet s)

POUR CHAQUE

v ≠ s FAIRE distance(v)  ∞ distance( s)  0

E  ∅

TANT-QUE E ≠S FAIRE

s  choisir({v  S | distance(v)=min{distance(x) | xS}})

E  E ∪ {

s}

POUR CHAQUE

v  A(s)SI distance( v) > distance(s) + p(s,v) ALORS distance( v)  distance(s) + p(s,v) père( v)  s

FIN SI

FIN POUR

FIN-TANT-QUEPreuve de correction ?

Complexité ?

THEG47colange@epita.lrde.frCalcul de distance dans un graphe pondéré positif :

Algorithme de Dijkstra (Schéma de preuve)

La preuve se fait par l'absurde en utilisant la propriété 1. Supposons que pour un sommet y avec la plus petite distance partielle, on ait d(s,y) ≠ distance(s,y). La distance partielle correspondant à la longueur d'un chemin dans le graphe, on a donc en fait l'inégalité d(s,y) < distance(s,y). Pour obtenir une contradiction considérons un plus court chemin c de s à y, et sur ce chemin intéressons nous au premier sommet y' n'appartenant pas à E que nous rencontrons en partant de s. La longueur du chemin c est par déifinition d(s,y); elle est aussi d'après le propriété 1 d(s,y') + l(y',...,y). Nous avons donc d(s,y') Cependant le sommet y' étant non marqué, de par notre choix de y nous avons distance(s,y) d(s,y') < distance(s,y'). Pour conclure intéressons-nous au sommet x précédant y' sur le

chemin c ; la propriété 1 implique que d(s,y') = d(s,x) +p(x,y'). Mais de par la déifinition de la

distance partielle, le sommet x appartenant à s, on a distance(s,y') CQFD.

THEG48colange@epita.lrde.frO(|S|)

O(|S|)

O(|A|)O(|S|2)

Cas d'une listecalcul de distance dans un graphe

pondéré positif : complexité O(|S|2+|A|)Distance-pondere-pos (graphe G=, sommet s)

POUR CHAQUE

v ≠ s FAIRE distance(v)  ∞ distance( s)  0

E  ∅

TANT-QUE E ≠S FAIRE

s  choisir({v  S | distance(v)=min{distance(x) | xS}})

E  E ∪ {

s}

POUR CHAQUE

v  δ(s)SI distance( v) > distance(s) + p(s,v) ALORS distance( v)  distance(s) + p(s,v) père( v)  s

FIN SI

FIN POUR

FIN-TANT-QUE

THEG49colange@epita.lrde.frcalcul de distance dans un graphe pondéré positif : complexité

O(|S|)

O(|S|)

O(|A|)O(|S|log(|S|) )

Cas d'un tas binaireO(|A|log(|S|) )

O((|A|+|S|)log(|S|) )Distance-pondere-pos (graphe G=, sommet s)

POUR CHAQUE

v ≠ s FAIRE distance(v)  ∞ distance( s)  0

E  ∅

TANT-QUE E ≠S FAIRE

s  choisir({v  S | distance(v)=min{distance(x) | xS}})

E  E ∪ {

s}

POUR CHAQUE

v  δ(s)SI distance( v) > distance(s) + p(s,v) ALORS distance( v)  distance(s) + p(s,v) père( v)  s

FIN SI

FIN POUR

FIN-TANT-QUE

THEG50colange@epita.lrde.fr Graphe pondéré avec poids négatif AB FECD HG4 2122
-4 -1037 -31 48
THEG51colange@epita.lrde.fr L'algorithme de Dijkstra est-il applicable ? AB FE-23 124
dA(F)=∞dA(E)=3dA(E)=0AB

FE-24dA(B)=4

AB

FE-234dA(B)=∞

dA(F)=∞dA(E)=∞AB FE3

124dA(B)=∞

dA(F)=∞dA(E)=∞dA(E)=0 AB FE-23 124
dA(F)=4dA(E)=3dA(E)=0AB

FE-2dA(B)=4

AB FE-23 124
dA(F)=4dA(E)=2dA(E)=0AB

FE-2dA(B)=4

La distance de F n'est pas correcte !

On peut modifier Dijkstra mais la complexité devient exponentielle. THEG52colange@epita.lrde.frCalcul de distance dans un graphe pondéré avec valeur négatives : Algorithme de Bellman-Ford

Principe :

L'algorithme de Bellman-Ford utilise le principe général de l'approximation successive, Contrairement à l'algorithme de Dijkstra, qui sélectionne le minimum à chaque itération, Bellman-Ford applique l'approximation sur tous les arcs et ce |S|-1 fois pour garantir que tous les chemins soient visités. THEG53colange@epita.lrde.frCalcul de distance dans un graphe pondéré avec valeur négatives : Algorithme de Bellman-Ford AB

FE-234dA(B)=∞

dA(F)=∞dA(E)=∞dA(E)=0AB FE3

124dA(B)=∞

dA(F)=∞dA(E)=∞Exemple : AB

FE-234dA(B)=4

dA(F)=∞dA(E)=3dA(E)=0 AB FE124 AB

FE-234dA(B)=4

dA(F)=4dA(E)=2dA(E)=0 AB

FE124AB

FE-234dA(B)=4

dA(F)=3dA(E)=2dA(E)=0 AB FE124 THEG54colange@epita.lrde.frDistance-pondere-neg (graphe G=, sommet s)

POUR CHAQUE

v ≠ s FAIRE distance(v)  ∞ distance( s)  0

POUR i = 1 à |S|-1 FAIRE

POUR CHAQUE (s,

v)  ASI distance( v) > distance(s) + p(s,v) ALORS distance( v)  distance(s) + p(s,v) père( v)  s

FIN SI

FIN POUR

FIN-TANT-QUECalcul de distance dans un graphe pondéré avec valeur négatives : Algorithme de Bellman-Ford

Preuve ?

Sa complexité ?

THEG55colange@epita.lrde.frAvant de donner une preuve de l'algorithme, nous allons donner quelques propriétés, dans le cas d'un graphe sans circuit absorbant,

qui nous seront utiles :

Lemmes

1. Les valeurs dist(s) ne peuvent que diminuer pendant le déroulement de l'algorithme.

quotesdbs_dbs20.pdfusesText_26

[PDF] algorithme du plus court chemin java

[PDF] algorithme du plus court chemin python

[PDF] algorithme et langage c

[PDF] algorithme et programmation

[PDF] algorithme et programmation en language c

[PDF] algorithme et programmation en pascal

[PDF] algorithme et programmation en pascal pdf

[PDF] algorithme et programmation python

[PDF] algorithme et structure de données 1

[PDF] algorithme et structure de données 1er année

[PDF] algorithme et structure de données 2

[PDF] algorithme et structure de données exercices corrigés pdf

[PDF] algorithme et structure de données pdf

[PDF] algorithme et structure de données pointeur

[PDF] algorithme exercice