TD d’algorithmique avanc ee Corrig e du TD 11 : Plus courts

Le problème du plus court chemin /exercices/corrigé/p1 Le problème du plus court chemin : exercices- corrigé I 0 0 1 0 2 0 3 0 4 0 1 2 1 1 2 2 2 1 3 2 3 1 Les sommets correspondent à l'état du stock à la fin de chaque période : par hypothèse, il peut être de 0, 1 ou 2 Les arcs sont associés aux décisions Initialement, le stock est

TD n o 8 - Recherche de plus courts chemins 1 Lalgorithme de

Les notations sont les suivantes : π[v] contient le prédécesseur de v sur le chemin (NIL s'il n'y en a pas), δ(u,v) est le poids du plus court chemin de u vers v ( ∞s'il n'existe pas), d[v] est une ariablev qui est une borne supérieure du poids du plus court chemin de s vers v (cf question 4) On dé nit le poids d'un chemin p = hv 0,v

TD d’algorithmique avanc ee Corrig e du TD 11 : Plus courts

Comme nous l’avons remarqu e en cours, tout sous-chemin d’un plus court chemin est lui-m^eme un plus court chemin et le probl eme des plus courts chemins v eri e bien la propri et e de sous-structure optimale : nous pouvons donc essayer de le r esoudre par programmation dynamique 1 On note d(m)

Plus courts chemins: algorithme de Floyd-Warshall

du plus court chemin entre i et j (s’il existe, D ij = +1sinon) et R ij est une table de routage Exercice 1: Algorithme de Warshall Dans un premier temps, on s’int eresse a calculer la cl^oture transitive, c’est a dire d eterminer s’il existe un chemin allant de i a j pour tout couple de sommets (i;j) 2X2 Les chemins de G peuvent

Résolution des problèmes de plus court chemin – exercices

Résolution des problèmes de plus court chemin – exercices- corrigé I Le graphe qui permet de modéliser ce problème est analogue à celui vu dans le cours C'est un graphe de 7 sommets numérotés de 0 à 6

SUJET + CORRIGE

Exercice 4: Variantes plus court chemin à origine unique (8 points) L’algorithmedeDijkstra Initialisation (G, s){ // G(S,A,w) oriente pour u dans S faire

Algorithmique — L3 — TD 9 Plus courts chemins : la méthode

Exercice 5 : Quelle est la complexité de cet algorithme (au mieux, au pire, en moyenne)? Exercice 6 : A quoi sert la dernière boucle? Donnez un exemple de graphe où la valeur FAUX est retournée Exercice 7 : Prouvez l’invariant S’il existe un plus court chemin de s à u de k arcs,

Correction sujet du bac en mathématiques, Inde, Pondichéry 2018

reemaths r Corrigé - Bac - Mathématiques - 2018 Déterminons le chemin le plus court qui permet à Louis de relier son domicile à son travail: Notons que: Louis souhaite aller de A à G Après recours à l’algorithme de Dijkstra, nous trouvons comme trajet que Louis doit suivre pour aller de A à G, tout en minimisant la distance ( chemin

Algorithmes de Graphes, HLIN501 Ann ee 2016-2017 L3 Info, L3

- Exercice 4 - Vrai/Faux Con rmer (et prouver) ou in rmer (et donner un contre-exemple) les propri et es suivantes : a Un sous-chemin d’un plus court chemin est un plus court chemin b Si r est un sommet d’un graphe orient e D pond er e par des longueurs positives toutes distinctes,

Universit´e Paris 7 - Master 1 Informatique - Intelligence

Exercice 1 Algorithmes de recherche (8 points) Consid´erez la carte suivante Le but est de trouver le chemin le plus court de A vers I A D E C H F G B I 5 5 6 2 5

TD d'algorithmique avancee

Corrige du TD 11 : Plus courts chemins pour tout couple de sommets

Jean-Michel Dischler et Frederic Vivien

Nous nous interessons ici a la recherche des plus courts chemins entre tous les couples de sommets d'un

graphe (typiquement on cherche a elaborer la table des distances entre tous les couples de villes d'un atlas

routier). On dispose en entree d'un graphe orienteG= (S;A) et d'une fonction de ponderationw. Nous

supposons que le grapheGpeut contenir des arcs de poids negatifs mais pas des circuits de poids strictement

negatifs. On notenle nombre de sommets deG(n=jSj), et on notef1;2;:::;nglesnsommets deG.

Programmation dynamique nave

Comme nous l'avons remarque en cours, tout sous-chemin d'un plus court chemin est lui-m^eme un plus

court chemin et le probleme des plus courts chemins verie bien la propriete de sous-structure optimale :

nous pouvons donc essayer de le resoudre par programmation dynamique.1.On noted(m) i;jle poids minimal d'un chemin d'au plusmarcs du sommetiau sommetj. Denissez recursivementd(m) i;j(la recursion portera ici sur le nombre d'arcs d'un plus court chemin). Pourm= 0il existe un plus court chemin sans arc deiversjsi et seulement sii=j: d (0) i;j=0sii=j;

1sinon.

Pourm1,d(m)

i;jest la longueur du plus court chemin deiajcontenant au plusmarcs. Soit un tel plus court chemin contient exactementmarcs et il est obtenu par concatenation d'un plus court chemin d'au plusm1arcs deia un sommetket de l'arc dekaj, soit il n'en contient au plus que m1et sa longueur est egale ad(m1) i;j. Par consequent : d (m) i;j= min d (m1) i;j;min1knn d(m1) i;k+wk;jo = min 1knn d(m1) i;k+wk;jo

la formule etant simpliee gr^ace a la propriete :wj;j= 0.2.Construisez, au moyen de la formule de recurrence obtenue a la question precedente, un algorithme

de calcul des longueurs des plus courts chemins pour tout couple de sommets, algorithme base sur le paradigme de la programmation dynamique.

On noteW= (wi;j)1i;jnla matrice des poids etD(m)=

d(m) i;j

1i;jnla matrice des poids des plus

courts chemins contenant au plusmarcs. Le calcul deD(m)a partir deD(m1)et deWse fait au moyen de l'algorithme ci-dessous :Extension-Plus-Courts-Chemins(D,W) n lignes(D) soitD0= (d0i;j)1i;jnune matrice carree de taillen pouri 1anfaire pourj 1anfaire1 d0i;j +1 pourk 1anfaire d

0i;j min(d0i;j;di;k+wk;j)

renvoyerD0 A partir de cet algorithme, la resolution du probleme est triviale :Plus-Courts-Chemins(W) n lignes(W) D (1) W pourm 2an1faire D (m) Extension-Plus-Courts-Chemins(D(m1);W) renvoyerD(n1)3.Quelle est la complexite de votre algorithme? L'algorithmeExtension-Plus-Courts-Cheminss'execute en(n3), a cause des trois boucles im-

briquees. Le co^ut total de resolution est donc en(n4).4.Executez votre algorithme sur le graphe de la gure 1.2314534-5-468721Fig.1 { Exemple de graphe oriente.La gure 2 presente un exemple d'execution de cet algorithme.D(1)=0

BBB@0 3 81 4

1011 7

14 01 1

21 5 01

1 1 16 01

CCCAD(2)=0

BBB@0 3 8 24

3 04 1 7

14 0 5 11

215 02

811 6 01

C CCCA D (3)=0 B

BBB@0 33 24

3 04 11

7 4 0 5 11

215 02

8 5 1 6 01

CCCAD(4)=0

BBB@0 13 24

3 04 11

7 4 0 5 3

215 02

8 5 1 6 01

C CCCAFig.2 { Sequence des matrices calculees parPlus-Courts-Chemins.Algorithme de Floyd-Warshall L'algorithme de Floyd-Warshall est un autre algorithme concu suivant le principe de la programmation dynamique.2

1.Ici la recursion n'a pas lieu sur le nombre d'arcs d'un plus court chemin, mais sur les sommets in-

termediaires de ces chemins, un sommet intermediaire etant un sommet autre que les extremites du chemin. Ici,d(k) i;jest la longueur du plus court chemin deiajn'utilisant comme sommets intermediaires que des sommets parmif1;2;:::;kg.

Denissezd(k)

i;jde maniere recursive. De deux choses l'une, un plus court chemin deiajn'ayant comme sommets intermediaires que des

sommets def1;2;::;kgcontient ou ne contient pas le sommetk:(a)Si le plus court cheminpdeiajet n'ayant comme sommets intermediaires que des sommets de

f1;2;::;kga eectivement comme sommet intermediairek, alorspest de la formeip 1 kp 2 j oup1(resp.p2) est un plus court chemin deiak(resp. dekaj) n'ayant comme sommets

intermediaires que des sommets def1;2;:::;k1g.(b)Si le plus court cheminpdeiajet n'ayant comme sommets intermediaires que des sommets

def1;2;::;kgne contient pask, alors c'est un plus court cheminpdeiajet n'ayant comme sommets intermediaires que des sommets def1;2;::;k1g. La structure explicitee ci-dessus nous donne directement une recursion denissantd(k) i;j: d (k) i;j=(w i;jsik= 0; min(d(k1) i;j;d(k1) i;k+d(k1)

k;j)sinon.2.Proposez un algorithme de calcul de la longueur des plus courts chemins base sur la recursion precedente

et le paradigme de la programmation dynamique.Floyd-Warshall(W) n lignes(W) D (0) W pourk 1anfaire pouri 1anfaire pourj 1anfaire d (k) i;j min(d(k1) i;j;d(k1) i;k+d(k1) k;j) renvoyerD(n)3.Quelle est la complexite de votre algorithme?

On remarque aisement que l'algorithme de Floyd-Warshall est de complexite(n3).4.Proposez un algorithme de construction eective des plus courts chemins a partir de l'algorithme

precedent.

Tout comme on a deni recursivement les longueurs des plus courts chemins, on peut denir recursivement

les predecesseurs dans les plus courts chemins :(k) i;jrepresente ici le predecesseur du sommetj dans le plus court chemin deiajn'utilisant comme sommets intermediaires que des sommets parmi f1;2;:::;kg. Pourk= 0, un plus court chemin ne possede aucun sommet intermediaire, donc : (0) i;j=Nilsii=jouwi;j=1; isii6=jetwi;j<1: Dans le cas general, si le plus court chemin est de la formei k jle predecesseur dejest le m^eme que celui du plus court chemin dekajet n'utilisant comme sommets intermediaires que des sommets parmif1;2;:::;k1g. Autrement, on prend le m^eme predecesseur dejque celui qui se trouvait sur le plus court chemin deiajet n'utilisant comme sommets intermediaires que des sommets parmi f1;2;:::;k1g. Nous avons donc, dans tous les cas : (k) i;j=((k1) i;jsid(k1) i;jd(k1) i;k+d(k1) k;j; (k1) k;jsid(k1) i;j> d(k1) i;k+d(k1) k;j:

Ce qui nous donne l'algorithme suivant :3

Floyd-Warshall(W)

n lignes(W) D (0) W pouri 1anfaire pourj 1anfaire sii=jouwi;j=1 alors(0) i;j=Nil sinon(0) i;j=i pourk 1anfaire pouri 1anfaire pourj 1anfaire sid(k1) i;jd(k1) i;k+d(k1) k;jalors d (k) i;j d(k1) i;j (k) i;j (k1) i;jsinon d (k) i;j d(k1) i;k+d(k1) k;j (k) i;j (k1) k;j renvoyerD(n)et (n)5.Executez votre algorithme sur le graphe de la gure 1. La gure 3 presente le resultat de l'execution de l'algorithme de Floyd-Warshall sur le graphe de la gure 1.4

D(0)=0

BBB@0 3 81 4

1011 7

14 01 1

21 5 01

1 1 16 01

CCCA(0)=0

BBB@Nil1 1Nil1

Nil Nil Nil2 2

Nil3Nil Nil Nil

4Nil4Nil Nil

Nil Nil Nil5Nil1

C CCCA D (1)=0 B

BBB@0 3 81 4

1011 7

14 01 1

2 55 02

1 1 16 01

CCCA(1)=0

BBB@Nil1 1Nil1

Nil Nil Nil2 2

Nil3Nil Nil Nil

4 1 4Nil1

Nil Nil Nil5Nil1

C CCCA D (2)=0 B

BBB@0 3 8 44

1011 7

14 0 5 11

2 55 02

1 1 16 01

CCCA(2)=0

BBB@Nil1 1Nil1

Nil Nil Nil2 2

Nil3Nil2 2

4 1 4Nil1

Nil Nil Nil5Nil1

C CCCA D (3)=0 B

BBB@0 3 8 44

1011 7

14 0 5 11

215 02

1 1 16 01

CCCA(3)=0

BBB@Nil1 1Nil1

Nil Nil Nil2 2

Nil3Nil2 2

4 3 4Nil1

Nil Nil Nil5Nil1

C CCCA D (4)=0 B

BBB@0 31 44

3 04 11

7 4 0 5 3

215 02

8 5 1 6 01

CCCA(4)=0

BBB@Nil1 4 2 1

4Nil4 2 1

4 3Nil2 1

4 3 4Nil1

4 3 4 5Nil1

C CCCA D (5)=0 B

BBB@0 13 24

3 04 11

7 4 0 5 3

215 02

8 5 1 6 01

CCCA(5)=0

BBB@Nil3 4 5 1

4Nil4 2 1

4 3Nil2 1

4 3 4Nil1

4 3 4 5Nil1

C CCCA Fig.3 { Sequence des matriceD(k)et (k)calculees par l'algorithmeFloyd-Warshallpour le graphe de la gure 1.5quotesdbs_dbs7.pdfusesText_13

[PDF] TD d’algorithmique avanc ee Corrig e du TD 11 : Plus courts

TD d'algorithmique avancee

Jean-Michel Dischler et Frederic Vivien

Programmation dynamique nave

1sinon.

Pourm1,d(m)

On noteW= (wi;j)1i;jnla matrice des poids etD(m)=

1i;jnla matrice des poids des plus

0i;j min(d0i;j;di;k+wk;j)

BBB@0 3 81 4

1011 7

14 01 1

21 5 01

1 1 16 01

CCCAD(2)=0

BBB@0 3 8 24

3 04 1 7

14 0 5 11

215 02

811 6 01

BBB@0 33 24

3 04 11

7 4 0 5 11

215 02

8 5 1 6 01

CCCAD(4)=0

BBB@0 13 24

3 04 11

7 4 0 5 3

215 02

8 5 1 6 01

1.Ici la recursion n'a pas lieu sur le nombre d'arcs d'un plus court chemin, mais sur les sommets in-

Denissezd(k)

Ce qui nous donne l'algorithme suivant :3

Floyd-Warshall(W)

D(0)=0

BBB@0 3 81 4

1011 7

14 01 1

21 5 01

1 1 16 01

CCCA(0)=0

BBB@Nil1 1Nil1

Nil Nil Nil2 2

Nil3Nil Nil Nil

4Nil4Nil Nil

Nil Nil Nil5Nil1

BBB@0 3 81 4

1011 7

14 01 1

2 55 02

1 1 16 01

CCCA(1)=0

BBB@Nil1 1Nil1

Nil Nil Nil2 2

Nil3Nil Nil Nil

4 1 4Nil1

Nil Nil Nil5Nil1

BBB@0 3 8 44

1011 7

14 0 5 11

2 55 02

1 1 16 01

CCCA(2)=0

BBB@Nil1 1Nil1

Nil Nil Nil2 2

Nil3Nil2 2

4 1 4Nil1

Nil Nil Nil5Nil1

BBB@0 3 8 44

1011 7

14 0 5 11

215 02

1 1 16 01

CCCA(3)=0

BBB@Nil1 1Nil1

Nil Nil Nil2 2

Nil3Nil2 2

4 3 4Nil1

Nil Nil Nil5Nil1