L'algorithme de Dijkstra consiste en la recherche des plus courts chemins menant d'un sommet unique s ∈ S à chaque autre sommet d'un graphe pondéré G = (S
| Previous PDF | Next PDF |
[PDF] TP 7 : algorithme de Dijkstra
Ce TP est consacré `a la programmation de l'algorithme de Dijkstra On enregistre un Si l'on implémente F comme une file de priorité, c'est-`a-dire un tasmin
[PDF] TP 4 Plus courts chemins Algorithme de Dijkstra - LIRMM
Algorithmes de Graphes, HLIN501 Année 2016-2017 TP 4 Programme en C ++ Votre programme La relation de filiation de l'arbre de Dijkstra return 0;
[PDF] Algorithme de Dijkstra - Normale Sup
21 oct 2008 · l'algorithme de Dijkstra sur des exemples concrets Exemple 1 Cherchons les plus courts chemins d'origine A dans ce graphe: A B E C D 10
[PDF] TD5 : Algorithme de Dijkstra - CNRS
Cet algorithme est adapté pour connaître les plus courts chemins depuis un c) Que se passera-t-il si vous appliquez l'algorithme de Dijkstra sur ce graphe ?
[PDF] Algorithme de Dijkstra : terminaison, correction et complexité
L'algorithme de Dijkstra est un grand classique pour calculer le plus court chemin dans un graphe à partir d'une origine unique Pour la correction de cet
[PDF] TP Informatique no 9/10 Algorithme de Dijkstra - Arnaud Jobin
L'algorithme de Dijkstra consiste en la recherche des plus courts chemins menant d'un sommet unique s ∈ S à chaque autre sommet d'un graphe pondéré G = (S
[PDF] Algorithme de Dijkstra
3 Dijkstra naïf 14 3 1 Header C'est le nombre de sommet du graphe */ 97 pour calculer à partir de l'algorithme de dijkstra le plus court chemin d'une
[PDF] Graphes et plus court chemin - Programmation 3
c b d t 12 4 2 1 15 17 4 12 13 3 11 Graphe non orienté voisins(u) = {v ∈ S {u L'algorithme de Dijkstra découvre à chaque étape de nouveaux chemins
[PDF] Comparaison dalgorithmes de plus courts chemins sur - Numdam
Sur des graphes à 15000 sommets, certains algorithmes sont jusqu'à 218 fois plus rapides que l'algorithme classique de Dijkstra Mots clés : Plus court chemin,
[PDF] Plus court chemin dans un graphe - mediaeduscoleducationfr
un chemin), et pondéré (c'est-à-dire que les arêtes sont accompagnées d'un poids, entier L'algorithme de Dijkstra opère sur un graphe connexe pondéré, pas
[PDF] algorithme de dijkstra java
[PDF] algorithme de dijkstra javascript
[PDF] algorithme dichotomie python
[PDF] algorithme factorielle boucle pour
[PDF] algorithme factorielle en c
[PDF] algorithme factorielle n
[PDF] algorithme factorielle pascal
[PDF] algorithme factorielle python
[PDF] algorithme fonction procedure exercice corrigé pdf
[PDF] algoritmo de dijkstra aplicaciones
[PDF] algoritmo de dijkstra c++
[PDF] algoritmo de dijkstra em c
[PDF] algoritmo de dijkstra grafos
[PDF] algoritmo de dijkstra online
BCPST-22016-2017
TPInformat iquen
o 9/10AlgorithmedeDijkstra
I.Quelques notionsdegraphes
L'algorithmedeDijkstraestunalgorithme permetta ntdedéterminerlespluscour tschemi ns entrecertainspo intsd'ungraphe.Ava ntdedétaillerlefoncti onnementdecetal gorithme,com- mençonsparintrodu irelevoca bulairenécessairesurlesgraphes.Définition
Onappel legrapheG=(S,A)uncouple où:
⇥Sestunen semble,a ppeléensembledessommets, ⇥Aestunep artiedeS⇥S,ap peléeensembledesarêtes.Danslasuite, onsupp oseraSfini.
Exemple
Oncons idèrelegraphesuivant,don népars areprésentationgraph ique. A BC D EF 3 1 1 3 2 5 3 1 1Legraphe G=(S,A)esticid éfinipar :
Remarque
Legra pheprésentéicipossède lescaractéristiquessui vantes. •Iln'est pasorienté:si(u,v)2Aalorsona (v,u)2A. Ainsi,sionpeutallerd euàv,al orsonpeutaussia llerdevàu. •Ilestsimple:il yaaupl usu nea rêteent redeuxsommets. •Ilestpondéré:àc haq uearêteonassocieune valeurpositiv eappelée poids. Cepo idsreprésenteladi stanceentrelesdeuxsommet s. 1BCPST-22016-2017
Définition
Onappel lematricedespoidsd'ungraphel amatriceG=(g
i,j (i,j)2S2tellequepourt out
coupledesommets(i,j): ⇥si(i,j)2Aalorsg i,j estégal aupoidsde l'arête (i,j), ⇥si(i,j)62Aalorsg i,j =+1.Exemple
Legrap heprécédentpossède6sommets.
Aprèsrenommage dessommets,lamatricedespoid sdecegr apheest:DBECFA
D B E C F A 0 B B B B B B B B B B B B031+1+1+1
3012+1+1
11035+1
+123013+1+15101 +1+1+1310 1 C C C C C C C C C C C C A Onpeut représentercett ematriceenPythonsouslaformed' untabl eaudetypearray.
1importnumpyasnp
23Inf=np.inf
5[Inf,2,3,0,1,3],[Inf,Inf,5,1,0,1],[Inf,Inf,Inf,3,1,0] ])
IQuelleremarquepeut -onfairesurlamatriced epoidsdecegraphe.C'estunemat ricesymétri que.
IDequel lepropriétéprovient cettecaractéristique?Legrap heprécédentn'estpasori enté.
Ainsichaquearête (u,v)fournitunearête(v,u)demême poids.II.Algori thmedeDijkstra
II.1.Brèvepré sentation
L'algorithmedeDijkstraconsisteenlarecher chedesp luscourtscheminsmenantd 'unsommet uniques2Sàch aqueautresommetd'u ngraphepondéréG=(S,A). TouslesarcsdeGsontsupposésd epoidspositifcequiperm etd'em pêcherlaprésencedecy cles depoid sstrictementnégati fs.Notation
Pourtoutt2S,onnomme(t)lalong ueurdupluscourtcheminmen antdesàt. 2BCPST-22016-2017
II.2.Calculde lalongueurdesplus courts chemin s
Avantdedéterminer lesplu scourtscheminsentresetto utautresommet t,on commencep ar déterminerlalongueurdecha cundeces pluscourtscheminsi.e.lafoncti on. Pourcefaire,onu til iseunattrib utd[v]dusomm etv2Squicontient lepoidsdusupposép lus courtcheminmena ntdesàv.Ceta ttr ibutestcorrigéaufuretàmesur edel'a lgorithmede sorteàcontenir(v)àla findel' exécution .Évid emment,cetattributest,àchaqueéta pede l'algorithme,unmajorantdupoidsd'unplu scourtc heminmenantdesàv.Au trementdit:8v2S,(v)6d[v]
Détaillonslafonctionnementdecetat tribut .
Miseàjourd el'attribu td[v]
1)Initialisation
Audébu tdel'algorit hme,onco nsidère:
⇥d[s] 0, ⇥d[v] +1pourtoutsomm ets2S.Exemple
Surl'exemp leprécédent,etsionchoisi ts=D,l' étaped'initialisat ions'écrit:DBECFA
0+1+1+1+1+1
2)Principederelâchement
L'opérationderelâchementd'unarc(u,v)2S⇥Sconsisteenuntestpermettan tde savoir s'ilestpossib le,enpas santparu,d' améliorerlepluscourtcheminjus qu'àv.Sioui ,ilfautmettreà jourd[v].
Plusprécisément ,one
ff ectueletests uivant : d[u]+g u,vExemple
1)Surl'exempleprécédent,onprendu=D
Oncherc healorsàdéterminer,p ourtoutsommetv2Ssionp eutmettr eàjoursd[v]à l'aided'unchemindon tledernierarc est(u,v). Étantdonnéel'étap ed'initialisat ion,celaconsisteàcons idérerlescheminsdesàvde taille1:DBECFA
031+1+1+1
3BCPST-22016-2017
2)Onprendalorsu=E
Oncher chealorsàdéterminer,p ourtoutsommetv2Ssionpeu tmettre àjoursd[v]à l'aided'unchemindo ntledernierarc est(u,v).Étantdonnéel'éta peprécédente,celaconsi steàconsidérerleschemin sdesàvdet aille
2(autrementditlescheminss!u!v):
DBECFA
02146+1
3)Onprendalorsu=B
Oncher chealorsàdéterminer,p ourtoutsommetv2Ssionpeu tmettre àjoursd[v]à l'aided'unchemindo ntledernierarc est(u,v).Étantdonnéel'éta peprécédente,celaconsi steàconsidérerleschemin sdesàvdetaille
3(autrementditlescheminss!...!u!v):
DBECFA
02146+1
4)Onprendalorsu=C
Oncher chealorsàdéterminer,p ourtoutsommetv2Ssionpeu tmettre àjoursd[v]à l'aided'unchemindo ntledernierarc est(u,v).Étantdonnéel'éta peprécédente,celaconsi steàconsidérerleschemin sdesàvdetaille
4(autrementditlescheminss!...!...!u!v):
DBECFA
021457
5)Onprendalorsu=F
Oncher chealorsàdéterminer,p ourtoutsommetv2Ssionpeu tmettre àjoursd[v]à l'aided'unchemindo ntledernierarc est(u,v).Étantdonnéel'éta peprécédente,celaconsi steàconsidérerleschemin sdesàvdetaille
DBECFA
021456
6)Onprendalorsu=A
Oncher chealorsàdéterminer,p ourtoutsommetv2Ssionpeu tmettre àjoursd[v]à l'aided'unchemindo ntledernierarc est(u,v).Étantdonnéel'éta peprécédente,celaconsi steàconsidérerleschemin sdesàvdetaille
DBECFA
021456
Sélectiondusommetuàchaqueétape
Àch aqueétapedel'algori thme,onsélectio nneles ommetuquivérifie lespropriétéssuiva ntes:
•un'apasencor eétésélectio nné, •l'attributd[u]estlepl usfaibl e(parmitous lessommetsnonencore sélectionnés). Onparled'algorit hmeglouton:on sélection neàchaqueétapelasous-sol uti onoptimalei.e.le sommetréalisantla meilleuredistance.Findel' algori thme
Unefoisto uslessommet svisités,on atrouv étouslespluscourtsc hemins(desàtoutv)de tailleinférieureouéga leaunombredesommetsent out.On adonctrouvé tousles pluscourts dechemi ns(desàtoutv). 4BCPST-22016-2017
II.3.Implémen tation
IAppliquerl'algorithmedeD ijkstraavecorigineD.
DBECFA
0+1+1+1+1+1
031+1+1+1
02146+1
02146+1
021457
021456
021456
IAppliquerl'algorithmedeDi jkstraavecorigineE.
DBECFA
IAppliquerl'algorithmedeD ijkstraavecorigineC.
DBECFA
5BCPST-22016-2017
IImplémenterDijkstraDist(G,depart)quiprendenp aramètrelama tri cedespoidsGetle sommetdepartetren voielatailledesplu scourts cheminsdedepartàto utsommetv.1defdijkstraDist(G, depart):
3N=np.size(G,0)
47pcc=list()
8foriin range(N):
9pcc.append([Inf,False])
10sommet_u= depart
11dist_u=0
12pcc[depart][0]=0
14pcc[depart][1]=True
1517cpt=0
18whilecpt !=N-1:
21minimum=Inf
22#Étapederelâchement
23forkin range(N):
2426ifpcc[k][1]== False:
27dist_uv=G[sommet_u][k]
28#Distancetotaleduchemins->...->u->v
29dist_totale=dist_u+dist_uv
3032ifdist_totale< pcc[k][0]:
33pcc[k][0]=dist_totale
3436ifpcc[k][0]< minimum:
37minimum=pcc[k][0]
38prochain_sommet_select=k
3940#Onatraitécomplétementunsommet
41cpt=cpt+1
4244sommet_u= prochain_sommet_select
45pcc[sommet_u][1]=True
46dist_u=pcc[sommet_u][0]
4748return(pcc)
6BCPST-22016-2017
II.4.Exhiberle spluscourtschemin s
IEnrepren antlesexemplesprécédents(av ecorig ineDpuisavecorigi neE),expli quercomment onpeuto btenirlespl uscourtscheminsàl'a idedesca lculsdetaill eprécédents. •Siàune étap e,d[v]aét émodifié,il fautserappelerdequels ommetuprovient cettemodifica tion. •L'idéeétantalorsq uel'arc(u,v)seraunarcd uplusco urtchemin . IModifierlepremiertableau (avecor igineenD)po urqu'ilprenne encomptecettenouvel le information.DBECFA
0+1+1+1+1+1
031D +1+1+1 02 E 14 E 6 E +1
02146+1
02145C 7