Le problème du plus court chemin : exercices- corrigé
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
Résolution des problèmes de plus court chemin – exercices
Le plus court chemin de 0 à 4 est le chemin 0 – 2 - 4 Il faut produire 4 unités en période 1 et 4 unités en période 3 III Les longueurs sont positives, on pourrait appliquer l'algorithme de Moore Dijkstra, mais on peut vérifier que ce graphe est sans circuit auquel cas il vaut mieux appliquer l'algorithme de Bellman qui
Exercices“Pluscourtschemins” :Correction
Exercices“Pluscourtschemins” :Correction 19 octobre 2016 1 2 3 Ilsuffitd’appliquerlafonctionlog surlespoids 4 L’algorithme reste le même, mais on met à jour l’étiquette d’un sommet v en faisant (v) :=
TD9 : plus court chemin dans un graphe
TD9 : plus court chemin dans un graphe Exercice 1 Un graphe orient e pond er e G est donn e par la matrice d’incidence sui-vante, ou les sommets du graphe sont s;a;b;c;d et t et ou il existe une ar^ete du sommet s 1 vers le sommet s 2 si et seulement si la case situ ee a l’intersec-tion de la ligne s 1 et de la colonne s
Lycée JANSON DE SAILLY Année 2017-2018 GRAPHES PLUS COURT
Année 2017-2018 GRAPHES: PLUS COURT CHEMIN Tle ES 4 EXERCICE 1 Le graphe ci-dessous indique les différentes liaisons entre plusieurs lieux Le long de chaque arête figure la distance en kilomètres séparant les différents lieux En précisant la méthode utilisée, déterminer le plus courtchemin possible pour aller deAàL A E I B F J C
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
Recherche Opérationnelle - LORIA
–soit ce plus court chemin passe par le sommet k+ 1 Dans ce cas il ne peut y passer qu’une seule fois (sinon il y a un circuit, de valuation totale positive par hypothèse sur le graphe, que l’on pourrait éliminer pour construire un chemin entre iet jplus court, ce qui serait absurde)
Algorithmes de Graphes, HLIN501 Ann ee 2016-2017 L3 Info, L3
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, alors D poss ede une unique arborescence des plus courts chemins issue de r c Dans tout graphe G non orient e, connexe et valu e positivement sur ses ar^etes, il existe un
Th´eorie des graphes et algorithmes - LACL
– plus court chemin – d´etection de circuit dans un graphe orient´e , d´etermination des composantes fortement connexes d’un graphe orient´e , tri topologique – ordonnancement remarque : dans les algorithmes qui seront d´ecrits, le terme FIN signifie une sortie du pro-gramme en cours d’ex´ecution 1
Travaux Diriges RO03
existe un chemin de k arcs entre i et j et 0 sinon 2 2 : On définit de même Bk la puissance k-ème matricielle Booléenne de B et l'on pose : B ^ k=I B B 2 B3 Bk Montrer que : B ^ k ij=1 s'il existe un chemin de k arcs au plus entre i et j et 0 sinon Montrer que l'on peut définir B ^ =limB ^ k pour k tend vers ∝ 2 3 : On pose de
[PDF] Plus de tant, il est tant
[PDF] plus fait douceur que violence
[PDF] plus grand centre commercial d'ile de france
[PDF] Plus grand commun diviseur
[PDF] plus grand commun diviseur pgcd
[PDF] Plus grand diviseur commun (devoir maison)
[PDF] PLUS GRAND DIVISEUR COMMUN ; NOMBRES PREMIERS ET NOMBRES PREMIERS ENTRE EUX
[PDF] plus grand ouragan de l'histoire
[PDF] plus grand roi de france taille
[PDF] plus grande colonie au 19 siecle
[PDF] Plus grande hauteur, avec une feuille CANSON!
[PDF] plus grande zone commerciale d'europe
[PDF] plus gros char d'assaut du monde
[PDF] plus gros compte instagram france
Algorithmes de Graphes, HLIN501Annee 2016-2017
TD 5 L3 Info, L3 Math-Info.- TD 5. Plus courts chemins - - Exercice 1 - On considere le graphe oriente et pondere suivant :a d gb e hc f22 3 11 10 1 15 7 6 14181. Utiliser l'algo de Dijkstra pour calculer une arborescence des plus courts chemins issue dea.
2. La longueur de l'arcgeest en fait -8. Refaire la question precedente. Que constatez vous?
3. Utiliser cette fois l'algorithme de Bellman-Ford pour trouver une arborescence des plus courts
chemins issue dea. On traitera les arcs selon l'ordre alphabetique.4. Une seconde modication a lieu, la longueur de l'arcfhest maintenant de 1 (la longueur de
geest toujours -8). Relancer l'algorithme de Bellman-Ford. Que constatez vous? - Exercice 2 - PCC pour DAG.On considere l'algorithme suivant :
Algorithme :ALGO
Donnees: Un graphe oriente acycliqueD= (V;E) donne par listes de voisins entrants, l:E!IR etrun sommet deD.Resultat: Deux fonctions :d:V!IR etpere:V!V.
1debut2Calculer un tri topologiquev1;:::;vndeD;
3pour tous lesx2Vfaire4d[x] +1;
5pere[x] x;6d[r] 0;
7pour tous lesi= 1;:::;nfaire8pour tous lesy2V ois(vi)faire9sid[y] +l(yvi)< d[vi]alors10d[vi] d[y] +l(yvi);
11pere[vi] y;1. Appliquer l'algorithme precedent sur le grapheD= (V;A) ouV=fa;b;c;d;e;f;gg,Aest
donne ci-dessous avec les longueurs associees etr=a.abacbebfbgcbcecfdceg l(:)-3514521166 1Algorithmes de Graphes, HLIN501Annee 2016-2017
TD 5L3 Info, L3 Math-Info.2. Que calcule ALGO?
3. Preciser la complexite de cet algorithme.
4. Prouver la validite de ALGO.
- Exercice 3 - Cycles orientes de poids negatif. SoitD= (V;A) un graphe oriente et!:A!IR une fonction de poids. a. Appliquer l'algorithme de Floyd-Warshall au graphe orienteDayant pour ensemble de sommets V=fa;b;c;dg, d'arcsA=fba;ac;cd;cb;bdget fonction de poids!(ba) =1,!(ac) = 3, !(cd) = 1,!(cb) = 8,!(bd) =8. Vous donnerez les plus courts chemins et leur longueur. b. M^eme question que precedemment mais apres avoir inverse la direction de l'arcbd(qui devient doncdb), tout en conservant son poids. c. Comment peut-on detecter la presence d'un cycle oriente de poids negatif apres l'execution deFloyd-Warshall?
- Exercice 4 - Vrai/Faux. Conrmer (et prouver) ou inrmer (et donner un contre-exemple) les proprietes suivantes : a. Un sous-chemin d'un plus court chemin est un plus court chemin. b. Sirest un sommet d'un graphe orienteDpondere par des longueurs positives toutes distinctes, alorsDpossede une unique arborescence des plus courts chemins issue der. c. Dans tout grapheGnon oriente, connexe et value positivement sur ses ar^etes, il existe un arbre des plus courts chemins deGqui est aussi un arbre couvrant de poids min deGde m^eme racine.d. Si un graphe oriente et value sur ses ar^etes possede certaines longueurs negatives, pour calculer
un arbre des plus courts chemins, il sut d'ajouterminfl(xy) :xy2Egsur chaque ar^ete puis d'utiliser l'algorithme de Dijkstra. e. Pour tout grapheGnon oriente, connexe et value sur ses ar^etes, et pour tout sommetrdeG, il existe un arbre des plus courts chemins issu der. - Exercice 5 - Coupes. Soientxetydeux sommets d'un graphe orienteD= (V;A) tel qu'il existe un chemin oriente dex ay. Un ensembleCAest unexy-coupesi tous les chemins dexaycontiennent un arc deC a. Montrer que siCest unexy-coupe, il existe un ensembleXde sommets tel queCcontient tous les arcs deXaVnX. b. Montrer que le nombre maximum dexy-coupes disjointes est egal a la longueur minimum d'un xy-chemin. - Exercice 6 - Arbitrage. L'arbitrageest l'utilisation du decalage entre les taux de change d'une monnaie pour transformer une unite de monnaie en plus d'une unite de la m^eme monnaie. Par exemple, si 1e= 1,51$U.S., 1$ U.S. = 0,62£et 1£= 1,11e, un speculateur peut, avec un euro, acheter 1;510;621;11 = 1;039 euros.