[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 estquotesdbs_dbs20.pdfusesText_26

[PDF] algorithme problème du plus court chemin

[PDF] algorithme programmation c

[PDF] algorithme programmation calculatrice

[PDF] algorithme programmation cours pdf gratuit

[PDF] algorithme programmation pascal exercices pdf

[PDF] algorithme programmation python

[PDF] algorithme tri à bulle java

[PDF] algorithme tri à bulle langage c

[PDF] algorithme tri a bulle python

[PDF] algorithme tri par selection python

[PDF] algorithmic bias in recruitment

[PDF] algorithmique et programmation c

[PDF] algorithmique et programmation en java cours et exercices corrigés pdf

[PDF] algorithmique et programmation en pascal

[PDF] algorithmique et programmation en pascal (résumé)