Le problème du plus court chemin : exercices- corrigé
Les sommets correspondent à l'état du stock à la fin de chaque période : par hypothèse il peut être de. 0
1 Plus court chemin
Dans tous les exercices on désignera par V (G) et E(G) respectivement l'ensemble des sommets et l'ensemble des arêtes d'un graphe G. Les variables n et m
Résolution de problèmes de plus court chemin/exercices/corrigé/p1
Résolution de problèmes de plus court chemin/exercices/corrigé/p1. Résolution des problèmes de plus court chemin – exercices- corrigé. I Le graphe qui permet
Résolution de problèmes de plus court chemin : Exercices
IV Déterminer dans le graphe suivant les plus courts chemins à partir du sommet a. Utiliser l'algorithme de Ford-Bellman ( préciser pourquoi cela est nécessaire)
CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE
Les temps de parcours. (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe. 1. Déterminer le plus court chemin en minutes
TD dalgorithmique avancée Corrigé du TD 11 : Plus courts chemins
Corrigé du TD 11 : Plus courts chemins pour tout couple de sommets. Jean Comme nous l'avons remarqué en cours tout sous-chemin d'un plus court chemin est lui ...
Plus courts chemin pour tout couple de sommets
est associative (voir exercice 25.1.4). On peut calculer D avec seulement «intermédiaires» d'un plus court chemin ;. Un sommet intermédiaire d'un chemin ...
1 Bellman
Dans tous les exercices on désignera par Dans la suite on notera dH(u
Travaux Diriges RO03
Le but de ce problème est de déterminer un second plus court chemin entre les sommets 0 et n-1 d'un graphe G=(XU
Le problème du plus court chemin : exercices- corrigé
Les sommets correspondent à l'état du stock à la fin de chaque période : par hypothèse il peut être de. 0
ALGR_5_PCC Tt couples sommets
Soit la longueur minimale d'un chemin d'au plus m arcs du sommet i au sommet j. Pour m = 0 il existe un plus court chemin sans arc de i vers j si et seulement
Résolution de problèmes de plus court chemin/exercices/corrigé/p1
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.
Théorie des graphes et optimisation dans les graphes Table des
Quel est le plus court chemin en nombre de kilomètres
GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir
Compilation réalisée à partir d'exercices de BAC TES 4) On utilise l'algorithme du plus court chemin de Dijkstra pour déterminer une chaîne qui minimise ...
Corrigé TD N° 2
Le graphe de l'exercice est planaire car on peut le représenter de la façon un problème de plus courts chemins d'un sommet vers tous les autres ...
TD9 : plus court chemin dans un graphe.
Exercice 1. Un graphe orienté pondéré G est donné par la matrice d'incidence sui- vante o`u les sommets du graphe sont s
CORRIGÉ EXERCICES TERMINALE ES ALGORITHME DE
Les temps de parcours. (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe. 1. Déterminer le plus court chemin en minutes
Diapositive 1
Le poids du chemin le plus court ?(uv) entre deux Beaucoup d'algorithme de calcul de plus court chemin ... Exercice: Algorithme de Dijkstra.
Travaux Diriges RO03
Exercice 1. Exercice 2. ... On dit que j est à distance k de i si k est la longueur du plus court chemin entre i et j on va dire que j appartient à Dk.
Algorithmes de plus
court chemin Heike Ripphausen-Lipa-BeuthUniversity of Applied Science -Berlin J.M. Adam -Université de Grenoble Alpes -GrenobleObjectif
Se familiariser avec les différentes
sortes de problèmes de plus court cheminSavoir quel algorithme peut être
appliqué efficacement pour quel type de problème de plus courts chemins2Heike Ripphausen-Lipa& Jean-Michel Adam
3Sommaire
Introduction
Algorithmede Dijkstra
Algorithmede Bellman-Ford
Algorithmede Floyd-Warshall
Heike Ripphausen-Lipa& Jean-Michel Adam
Problème: trouverle cheminle plus court
ABTrouverle plus courtcheminde A à B
0 5Introduction
On considèreungrapheorientépondéré:
Graph G = (V,E)avec
Fonctionpoidsw: E -> R
(les poidsdes arcssontdes nombresréels)Heike Ripphausen-Lipa& Jean-Michel Adam
6Définition: Poidsd'unchemin
Le poidswd'uncheminpavec
p = (v 0 , v 1 , ... , v k )et (v i , v i+1 ) ɽEEstdéfiniainsi:
i=1..k w(v i-1 , v iHeike Ripphausen-Lipa& Jean-Michel Adam
7Definition: poidsdu cheminle
plus court Le poids du chemin le plus court į(u,v)entre deux sommetsuet vestdéfiniainsi: min { w(p): pestuncheminde uà v dansG }, si uncheminexisteį(u,v)=
, sinonHeike Ripphausen-Lipa& Jean-Michel Adam
8Idée de base pour trouver le chemin le
plus court De nombreux algorithmes de calcul de plus court chemin utilisent la propriétesuivante : Les sous-chemins des chemins les plus courts sont eux-mêmes les chemins les plus courts!Plus précisément:
si p =(v 0 , v 1 , ... , v k )est un chemin le plus court entre les sommets v 0 et v k alors pour iet j(le chemin p ij = (v i , v i+1 , ..., v j )est le chemin le plus court du sommet v i au sommet v jHeike Ripphausen-Lipa& Jean-Michel Adam
9Idée de base pour trouver le chemin le
plus court Nous nous concentrons sur le problème des chemins les plus courts d'une source unique, c'est-à-dire que l'on calcule les chemins les plus courts du sommet de départ svers tous les sommets v du graphe. Beaucoup d'algorithme de calcul de plus court chemin utilisent la technique de relaxation : A chaque sommet von associe un attribut distqui donne une borne supérieure de la distance du plus court chemin d'un sommet s(la source) au sommet v.Heike Ripphausen-Lipa& Jean-Michel Adam
10Relaxation
La méthode relaxationd'un arc(u,v)consiste à voir s i le chemin le plus court calculé jusqu'à vpeut être amélioré en prenant le chemin le plus court actuel de svers u, en lui ajoutant l'arc (u,v):Heike Ripphausen-Lipa& Jean-Michel Adam
11 initialisation-Source-Unique // Initialisationd'unalgorithmede relaxation // pourla recherchedes plus courtschemins // depuisunesourceunique: le sommets initialisation-Source-Unique(G, s) pourtoutsommet v de G dist[v] VMAX // valeurréellemax pred[v] NIL fpour dist[s] 0Heike Ripphausen-Lipa& Jean-Michel Adam
12Relax(u,v,w)
Relax(u, v, w)
// arc(u,v), w(u,v) estle poidsde l'arc sidist[v] > dist[u] + w(u,v) alors dist [v] dist[u] + w(u,v) pred[v] u fsiHeike Ripphausen-Lipa& Jean-Michel Adam
Algorithme de Dijkstra
(publication 1959) 14Algorithme de Dijkstra
L'Algorithme de Dijkstra résout le problème
des chemins les plus courts depuis une source unique, le sommet s.L'Algorithme de Dijkstrane fonctionne que
pour des poids positifs.Il fonctionne de manière similaire au
parcours en largeur, mais au lieu d'utiliser une file, il utilise une file prioritaire.Heike Ripphausen-Lipa& Jean-Michel Adam
15Algorithme de Dijkstra
L'algorithme de Dijkstra gère un ensemble (virtuel) S qui contient tous les sommets pour lesquels les distances les plus courtes depuis s sont déjà calculées.Etapepar étape, le sommetude Sdontla valeur
distestminimale, estsélectionéet tousles arcs u,v incidentsà u sontrelaxésPourgérerl'ensembleS, des sommetsdontla
distanceminimale depuiss n'apasencoreété déterminée , on utilisela fileprioritaireQ.Heike Ripphausen-Lipa& Jean-Michel Adam
16Algorithme de Dijkstra
Dijkstra(G, w, s)
initialisation-Source-Unique(G, s)S Ø; // tous les sommets atteints depuis s
Q tous les sommets // tous les sommets dans Q
tantque u Extraire-Min(Q) // sommet dont distminimaleS S.ajouter(u)
pourtout sommet v adjacent à uRelax(u,v,w);
fpour ftqRemarque: l'ensemblede sommetsS n'est
pas vraimentutile; ilestintroduitpour mieuxillustrerl'algorithme.Heike Ripphausen-Lipa& Jean-Michel Adam
17 sa bc d e 2 1 331 51
2 i
Valeurde dist: i
Vide : VMAX
0 sabcde Remarque : Q estordonnéeselonles valeurscroisantesde distAlgorithme de Dijkstra
File prioritaireQ
Heike Ripphausen-Lipa& Jean-Michel Adam
18 sa bc d e 2 1 331 51
2 0 bacde
File prioritaireQ
12Les sommetsde S sontcolorésen noir
Algorithme de Dijkstra
Heike Ripphausen-Lipa& Jean-Michel Adam
19 sa bc d e 2 1 331 51
2 0 adce12 2
Algorithme de Dijkstra
File prioritaireQ
Heike Ripphausen-Lipa& Jean-Michel Adam
20 sa bc d e 2 1 331 51
2 0 12 252
dce
Algorithme de Dijkstra
File prioritaireQ
Heike Ripphausen-Lipa& Jean-Michel Adam
2 21sa bc d e 2 1 33
1 51
2 0 12 42
7 ce
File prioritaireQ
Algorithme de Dijkstra
RelaxHeike Ripphausen-Lipa& Jean-Michel Adam
2 22sa bc d e 2 1 33
1 51
2 0 e12 42
5
Algorithme de Dijkstra
File prioritaireQ
Heike Ripphausen-Lipa& Jean-Michel Adam
23sa bc d e 2 1 33
1 51
2 0 12 242
5
Algorithme de Dijkstra
File prioritaireQ
Heike Ripphausen-Lipa& Jean-Michel Adam
Algorithme de Dijkstra dans une table
24sommetsabcde predNILNILNILNILNILNIL dist0
Initialisation
Après
avoirsupprimés de Q sommetsabcde predNILssNILNILNIL dist021Heike Ripphausen-Lipa& Jean-Michel Adam
25sommetsabcde predNILssNILbNIL dist0212
Après
avoirsuppriméb de QAprès
avoirsuppriméa de Q sommetsabcde predNILssabNIL dist02152Algorithme de Dijkstra dans une table
Heike Ripphausen-Lipa& Jean-Michel Adam
26Après
avoirsuppriméd de QAprès
avoirsuppriméc de QAlgorithme de Dijkstra dans une table
sommetsabcde predNILssdbd dist021427 sommetsabcde predNILssdbc dist021425Heike Ripphausen-Lipa& Jean-Michel Adam
27Après
avoirsupprimée de QAlgorithme de Dijkstra dans une table
Déterminationdu plus court cheminde s à e :
e c d b s sommetsabcde predNILssdbc dist021425Heike Ripphausen-Lipa& Jean-Michel Adam
28Exercice: Algorithme de Dijkstra
sa db e c 1 7 331 38
1 6 Avec l'algorithmede Dijkstradétermineztousles Chemins les plus courts partantdu sommets
Heike Ripphausen-Lipa& Jean-Michel Adam
29Temps d'exécution de
l'algorithme de DijkstraInitialize-Source-Unique(G, s)
S quotesdbs_dbs1.pdfusesText_1[PDF] exercice corrigé portique isostatique
[PDF] exercice corrigé préparation d'une solution tampon
[PDF] exercice corrigé probabilité jeu de 32 cartes
[PDF] exercice corrigé probabilité loi normale
[PDF] exercice corrigé probabilité stmg
[PDF] exercice corrigé probabilité variable aléatoire continue
[PDF] exercice corrigé propagation des ondes electromagnetique
[PDF] exercice corrigé pythagore
[PDF] exercice corrigé radar
[PDF] exercice corrigé raisonnement par récurrence terminale s pdf
[PDF] exercice corrigé recherche opérationnelle simplexe
[PDF] exercice corrigé redressement monophasé non commandé
[PDF] exercice corrige redressement simple alternance
[PDF] exercice corrigé redresseur triphasé
