ࡱ> /*+,-.Fhkڅ}TJFIFHHCCG" }!1AQa"q2#BR$3br %&'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz w!1AQaq"2B #3Rbr $4%&'()*56789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz ?>o^]|MEPEPEPEPEPEPEPEPEPEPEPEPEP_K/-~<[{g+&M_ZydR PEQEW|U/P1%+@u_ƪb>o^ ( ( ( ( ( ( ( ( ( ( ( ( ( 6YkK<)_5m%xR<&( 7Yx_:TƷ~'{{H巷A/=W[Z H\eDKo/ ⿇Z6 &YmcKAukye5͝ݼ]kRI"I.L{jҀ|+x^I5}N vq>^m߶i-"m>k)vEdtfGGR++UHA)b_|%Kx#CvӴGR}/-XEg,i͌M5<Zlb_jQD~ǿ#IZ𶱢xLJY-߄LZ[Y갶a'/'uk K( (n1'fo~8M>P6r-D>7R);m5ݰD7l`Aߵ?=;WU+{E_ oUuRuŵV憈ϖ_h_W7)x[3H_˫}ؚldoټߴ7PEP^>Og[=?&eghlcW:_XmcOnm0xN/G2tށJԂB7?X[.lF E椰4Rǿi@Q@Q@Q@Q@Q@Q@~,m̚6YkK<)@EPڟ΃ ~2IwÞt-+O4R ^.l5D5yh6VO:(M|G?_]{ ;K:szfgO+46}GqB1Ư++>T6U[,B+/ëOi>/UТ`d[Ӗgth5:kӡkyຆ)5i+|:>:/ox'#dzމ}$4i{ BO[Yw0*y@![G;a4XTI}bIrt3XXmm1*sK^]OO<{׺x.-)dV> Kk ]5}"A쬭/m_iƳ~k_hT?u_jsg?xkǺf;4յխ W}ԺA[j`C iiվ4]|'O-f Wt?5_>4E.qs&hqj'ZlX[ku_js?~5>>2VAڷwVilyn59.[L 3q$(%ĒD#i4퇎k携rm5<:ԖYEԮ5Kg&GcȺ~YkxZ.·u}V}BQ3[[Fzs>i=坭z .o&x`fosw?x~L{M[o]{ޑ0Z.!0 +~ş j17ėΝ? k7"BnOBh"Dco5ʖM4?W>kޓn{뚅[%WYETVZq-vϫQjv㉾,p^jw<~f::~iFiwqwg_\miupyHʟN@C:5u@Sqx߅Wi;#-$:6q5X-u}ȗ"Lpgg_OG<{.--fUKɮ}?WM[HЬ,/Է/cWScvΖkoSu_js&k>ū͡<+kOm>fҬ5;}6]3S,4˩.CzH~8|)Mv85/URQz< KJbUe9L!U'UfW?n]3g?i~#ִ֤ ^cutmP;=ݍίoNè*yMXm7Z}XԼ?VKmIF5-*#% {IVE lE3dV@W'UfW?nW\tƭyXi>nuxH L{0imhhb;$ִa$UD?>!]B찋׳bmOKӵi9FTRKE{y0'UfW?nW\ڻXhzyXm MGUYiͪɡKimm{:i1̓LRW,:>[Do^bjZX?]N}j:mcoV*U#4_:5ua.l/@>+ "(,B HRqkOTl<|!|c-wwAe 5kjY^w:ArZ[N#K?u?>-掚r-赸ִv,] [[SR%T@?]ϵQ1gv~%l [qR_>:V{I44VڡUSVot;;;+k>84;Xݗ[Dnq2.+xJ&5"{1o4xgVFBU㶸R40E׆:iVVwyx:&}zE-|S4os-79EI,<k}Wxk߈~7_e[MIM6shV7fwi/Lv<7_ɫxS?ſ ud w'Mߌ&ӆ'!NzhɪXںq۾ ( w񶚾 =<7q+Oշ+ۭ'7~+=oēkZ+Ykw=^ھen` g'E? |r~5T.SywCƉ)-5 ;se#~u~nSPu/)?~;|]T>#~m?MyZC ZxSÖ:FsUL4}Qn͊k_ ~9Ѿ*Xx_xZO=No {ž(j>;suih:=׉ nl5)&m _7P]s6Y迳+ |@U|?RM\M]5K1 jDŽ|SMַ|>=J%ygkxm[Qn$X8=v< {\|{ll#yiJ MZ4ΏK-niYۘn%P.osq/w|Im5-n᷈[y4[xO¶:JE:fv74iP{=/Kgį {xgޑo3VK4۩]o%|w>-ZCլRuX K%KYYG?Ÿ&wY_SW k>"^AivZ~(}M5l4?E9X[MBmE{@i;BO#ƞ <1>'u߈o ^%/ΟZ.t.4ۛ˳7I -Y|b~(_͖hԴ+O~% n,uI%d][jzl á[e(~2~ΗIr;χ?}'> l ݼGi:ܒ9oN'xhNɩ=(>$C}#|mw~9izLnOw]Kwڮ_ikc5;]"HV:\ y-J(OO?Wb5C>56fj&ajm>Ǩ$C}#|mw~9izLnOw]Kwڮ_ikc5;]"HV:\ y-J('ß=f;5W Og=7JYk-4!Tzƹ7z%?أRo9&O ^wy(o,iu& NѤ|Z~jj~5t_e~5Xx.%Kk[1O_↛^$=Oޑ"GC{5׭u/({=bZaꯩ}_] ɣzΥ8w|{᫟>kövusx.xMZXƟm_[˹{yfzxAe|;Y2Y=u/jgm-(t="9ZO\ p-䶹(_ %xS⇎yƧ|H4O:wíKþt'_mome~ư1iI<͞އ'KŃAOt=F5Zh ҡi8:y _W og_ΫZ,aHZܚ텓i>G}g,Yb?kQy=Ϣil"g}ۏ^g@uŧ;+~.Wă_C vu :'?Z 9t=k?{^u9&o)Onk:Mq09\<[_ xvU\k> 犴oRx5M?\%ۇkkƛܗ1Wڎ1E`!O&B@n@ xmN0oHԆDRu@ J <E*?R Tb(bc%<13 y $T+'{Ad -zhNtdLI(i Kgc0%, $Rx죒x&awp~4T,Q |#)d-]X5$~ GUBe'?&SCӍ٩%S4}J#IS#_EIZ%ik1dsJAޙ[jP#/97yR/lY&ypLbbTŮ,1ު7%IL%e'; z}N8Fqe|{( D  Equation Equation.30,Microsoft Equation 3.0F/ 0|DArialew RomanllrT0DWingdingsRomanllrT0 DTimes New RomanllrT00D[SOes New RomanllrT0@DSymbolew RomanllrT0 B .  @n?" dd@  @@`` h ` V4FL FG &%%%%%%%%#@<d)******HIJK0LMPzQ@R?S?TUUVWXYZ[\]^4_`*ab,c,d-e,mopqrst#uv}8KII/XR$hkڅ}T2$O&B@n 0e0e A@A5%8c8c     ?1d0u0@Ty2 NP'p<'p@A)BCD|E?@89 : 3  oO ʚ;5q8ʚ;g4kdkd讒 T0pppp@ <4!d!d8!0lr<4dddd8!0lr<4BdBd8!0lr h___PPT2001D<4X ___PPTMac11 @f   hnamd` Arial&Monotype Typography    hnamd` Arial&Monotype Typography    hnamd` Arial&Monotype Typography    hnamd` Arial&Monotype Typography    hnamd` Arial&Monotype Typography  ,namd$ Times Romant   hnamd` Arial&Monotype Typography   x   x     hnamd` Arial&Monotype Typography  0___PPT10 pp?\-19/7/2006 .Algorithmes de graphesO =_A"Module 5 : Algorithmes de graphes##( # Plan du module Arbre couvrant minimum Algorithme de Prim Algorithmes de plus court chemin Algorithme de Dijkstra Algorithme de Floyd Problme 10034`!+!+  Arbre couvrant minimum  Un arbre couvrant pour un graphe non-orient G est compos de tous les sommets de G avec un sous-ensemble des artes de G qui Relient les sommets; il existe un chemin entre tous les sommets de l arbre couvrant Forment un arbre sans racine, non ordonn, sans cycle. L~m   Arbre couvrant minimum  yUn arbre couvrant minimum est un arbre couvrant dont la somme des tiquettes (valeurs attaches aux artes) est minimale.&zay  Arbre couvrant minimum Arbre couvrant minimum Algorithme de Prim L arbre est construit nSud aprs nSud partant d un nSud initial chaque itration un nSud est ajout l arbre couvrant On ajoute toujours le nSud reliant l arbre avec l arte de moindre poids&  Arbre couvrant minimum Arbre couvrant minimum  Arbre couvrant minimum  Arbre couvrant minimum  Arbre couvrant minimum  Arbre couvrant minimum  Arbre couvrant minimum  FOR i := 0 TO g.nvertices-1 DO BEGIN intree[i] := false; distance[i] := MAXINT; parent[i] := -1 END; distance[start] := 0; v := start; WHILE NOT intree[v] DO BEGIN intree[v] := true; FOR i := 0 TO g.degree[v]-1 DO BEGIN w := g.edges[v][i].v; weight := g.edges[v][i].weight; IF (distance[w] > weight) AND NOT intree[w] THEN BEGIN distance[w] := weight; parent[w] := v END END; P   v := start; dist := MAXINT; FOR i := 0 TO g.nvertices-1 DO BEGIN IF (NOT intree[i]) AND (dist > distance[i]) THEN BEGIN dist := distance[i]; v := i END END P  Algorithmes de plus court chemin!!(   *Soit un graphe orient ou non ayant des tiquettes sur les artes pour reprsenter leur longueur. On veut connatre la distance minimale entre deux sommets. En gnral, la distance minimale d un sommet u au sommet v est la distance minimum de tous les chemins de u v.Z  Algorithme de Dijkstra  C est l algorithme de choix pour trouver le chemin de distance minimum entre deux nSuds d un graphe. Cet algorithme calcule le plus court chemin entre un nSud donn et tous les autres d un graphe. Ne fonctionne que sur des graphes sans artes ngatives.Z  Algorithme de Dijkstra  pL ide de base est trs semblable l algorithme de Prim. chaque itration, on ajoute un nSud l arbre de nSuds pour lequel nous connaissons le plus court chemin depuis la source s.  Algorithme de Dijkstra   Mais dans le problme du plus court chemin : nous ajoutons un nSud qui est le plus proche en distance de la source s Cette distance est fonction du poids de la nouvelle arte et de la distance depuis la source s de l arbre de nSuds auquel l arte est adjacente.&--  Algorithme de Dijkstra  Algorithme de Dijkstra  Algorithme de Dijkstra  Algorithme de Dijkstra  Algorithme de Dijkstra  Algorithme de Dijkstra  Algorithme de Dijkstra  BEGIN FOR i := 0 TO g.nvertices-1 DO BEGIN intree[i] := false; distance[i] := inf; parent[i] := -1 END; distance[start] := 0; v := start; WHILE NOT intree[v] DO BEGIN intree[v] := true; FOR i := 0 TO g.degree[v]-1 DO BEGIN w := g.edges[v][i].v; weight := g.edges[v][i].weight; IF (distance[w] > distance[v]+weight) AND NOT intree[w] THEN BEGIN distance[w] := distance[v]+weight; parent[w] := v END END; P   v := 0; dist := MAXINT; FOR i := 0 TO g.nvertices-1 DO BEGIN IF (NOT intree[i]) AND (dist > distance[i]) THEN BEGIN dist := distance[i]; v := i END END END; print_shortest_paths(g,0) END; P !Algorithme de Floyd FTrouver tous les plus courts chemins entre toutes les paires de nSuds d un graphe. Le graphe peut contenir des artes ngatives, mais pas de cycle cot ngatif TP  Algorithme de Floyd  Reprsentation du graphe : Une matrice de poids W(i,j)=0 si i=j W(i,j)= s il n y a pas d arte entre i et j W(i,j) =  poids de l arte fYA   "Algorithme de Floyd #Algorithme de Floyd Comment dfinir la distance la plus courte di,j en termes de problmes plus  petits ? Une faon de faire consiste se limiter des chemins n incluant que des nSuds d un sous-ensemble restreint. 4+ %Algorithme de Floyd  4Initialement, ce sous-ensemble est vide. Ensuite il est augment progressivement, un nSud la fois, jusqu ce qu il contienne tous les nSuds du graphe. (  $Algorithme de Floyd Soit D(k)[i,j]=poids du plus court chemin de vi vj n utilisant que les nSuds {v1,v2,& ,vk} comme nSuds intermdiaires dans le chemin D(0)=W D(n)=D c est la matrice finale Comment calculer D(k) depuis D(k-1) ? &' , &Algorithme de Floyd RCas 1: Un plus court chemin de vi vj limit aux nSuds {v1,v2,& ,vk} comme nSuds intermdiaires n utilise pas vk. Alors D(k)[i,j]= D(k-1)[i,j]. Cas 2: Un plus court chemin de vi vj limit aux nSuds {v1,v2,& ,vk} comme nSuds intermdiaires utilise vk. Alors D(k)[i,j]= D(k-1)[i,k]+ D(k-1)[k,j]. )     +       "     &            * 'Algorithme de Floyd Comme D(k)[i,j]= D(k-1)[i,j] or D(k)[i,j]= D(k-1)[i,k]+ D(k-1)[k,j]. On obtient: D(k)[i,j]= min{ D(k-1)[i,j], D(k-1)[i,k]+ D(k-1)[k,j] }X                           6C :(Algorithme de Floyd  )Algorithme de Floyd 6D1[2,3] = min( D0[2,3], D0[2,1]+D0[1,3] ) = min (, 7) = 7 D1[3,2] = min( D0[3,2], D0[3,1]+D0[1,2] ) = min (-3,) = -3         P+/ *Algorithme de Floyd D2[1,3] = min( D1[1,3], D1[1,2]+D1[2,3] ) = min (5, 4+7) = 5 D2[3,1] = min( D1[3,1], D1[3,2]+D1[2,1] ) = min (, -3+2) = -1        @E+Algorithme de FloydD3[1,2] = min(D2[1,2], D2[1,3]+D2[3,2] ) = min (4, 5+(-3)) = 2 D3[2,1] = min(D2[2,1], D2[2,3]+D2[3,1] ) = min (2, 7+ (-1)) = 2          DF,Algorithme de Floyd 1. D W // initialiser D avec les poids des artes 2. P 0 // initialiser P 0 3. for k 1 to n 4. do for i 1 to n 5. do for j 1 to n 6. if (D[ i, j ] > D[ i, k ] + D[ k, j ] ) 7. then D[ i, j ] D[ i, k ] + D[ k, j ] 8. P[ i, j ] k; D*H'Algorithme de Floyd  Pourquoi peut-on travailler sur une mme matrice ? D[i,j] ne dpend que des lments de la kime ligne et kime colonne de la matrice. La kime ligne et kime colonne de la matrice restent inchanges lorsqu on calcule Dk33#@&3  Algorithme de Floyd  Les lments de la diagonale principale restent 0 car : D(k)[ j,j ] = min{ D(k-1)[ j,j ] , D(k-1)[ j,k ] + D(k-1)[ k,j ] } = min{ 0, D(k-1)[ j,k ] + D(k-1)[ k,j ] } = 0 :                 &:   Algorithme de Floyd  La kime colonne de Dk est gale la kime colonne de Dk-1 : Pour tout i D(k)[i,k] = min{ D(k-1)[i,k], D(k-1)[i,k]+ D(k-1)[k,k] } = min { D(k-1)[i,k], D(k-1)[i,k]+0 } = D(k-1)[i,k]         1Algorithme de Floyd  La kime ligne de Dk est gale la kime ligne de Dk-1 : Pour tout i D(k)[k,j] = min{ D(k-1)[k,j], D(k-1)[k,k]+ D(k-1)[k,j] } = min{ D(k-1)[ k,j ], 0+D(k-1)[k,j ] } = D(k-1)[ k,j ] G                        2Algorithme de Floyd  6 FOR k := 1 TO g.nvertices DO FOR i := 1 TO g.nvertices DO FOR j := 1 TO g.nvertices DO BEGIN through_k := g.weight[i,k]+g.weight[k,j]; IF through_k < g.weight[i,j] THEN BEGIN g.weight[i,j] := through_k; p[i,j] := k END END 7P77 Problme 10034  ^In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle. _Z__ Problme 10034  Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles. PPPP Problme 10034  @Sample Input 1 3 1.0 1.0 2.0 2.0 2.0 4.0 Sample Output 3.41 APAA /p^ 0` 33PP` 3333` ___MMM` 13` 333fpKNāvI` j@v۩ῑ΂H` Q_{>?" dd@,?n<d@ `7 `2@`7``2 n?" dd@   @@``PR    @ ` ` p>>   . (    <" @   T|d" @   <8"U_ @   T d">& @   N"P @   <"p @   S ~?d?"" @   6  "U  T Click to edit Master title style! !$  0 "   RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6p  "@  P*   6, "@`   R*   6 "`  R* `  C *ALogo CIL"`PB  s *޽h ? 3333  Blends   0 S K  (  ZZ P@ # "Dwoh  s *"PP  Bd" P@ZZ P 0  # "Nyh  s *"P    Bd"P 0 x   B" a*f   0"   <T ?"pP  T Click to edit Master title style! !   04 " `    W#Click to edit Master subtitle style$ $  6 "`p   T*   6 "`p   V*   6 "`  V*   S ~?d?" %& @ `  C *ALogo CIL"`PB  s *޽h ? 3333 0 `(    0`7 P    T*    0DQ     V*  d  c $ ?    0tU  0  RClick to edit Master text styles Second level Third level Fourth level Fifth level!    S   6Z _P   T*    6_ _   V*  H  0޽h ? 3380___PPT10.P%\w 0 0|( d |l | C $ pP  r | S \  `    H | 0޽h ? 3333___PPT10i.r'+D=' = @B +$  0 $(  r  S ; U   r  S P>    H  0޽h ? 333380___PPT10.ALB$  0 $(  r  S TB U   r  S ,C    H  0޽h ? 333380___PPT10.02$  0 $(  r  S lK U   r  S DL    H  0޽h ? 333380___PPT10.՗| 0 ,$//(  ~  s *S U   G F p@pP   p00 2  0pp0`  5a 2  0 ` P  5c 2  0Ȅ   5e 2  0P @  5d 2  0 pp` 5b Z   s *=  SZ   s *@ = 8Z   s * x ` `   01= P 8`   01 s `  01  ` B 01 ` Z B s * H   < QJ 8 72   < T  74   <|@  75   < @ ' 79   <D 9`  76   <T Y` @ 74   <Ȧ   75   <4 YD@ 75 G F  p    p  2  0L `P 5a 2  0|   5c 2  0@ 0  5e 2  0ػ 5d 2  00  5b Z  s * 0Z   s *mShZ ! s * P( ` " 0p -h` # 0p}# ` $ 0pc# ` %B 0p Z &B s *x @  ' <`6h 72  ( <@ 74  ) <,   75  * <<pPW 79  + <LiP 76  , <Lp 74  - < P  75  . <h0p 75 X / 0G4 H  0޽h ?         ! " #$%& ̙33$  0 $(  r  S  *a U  a r  S *a   a H  0޽h ? 333380___PPT10.äp+.L[  0 a[Y[x٤X(  ~  s *4a U  a G F p@pP   p00 2  04=ap0`  5a 2  0H ` P  5c 2  0t.a   5e 2  0CaP @  5d 2  0Ga pp` 5b Z   s *=  SZ   s *@ = 8Z   s * x ` `   01= P 8`   01 s `  01  ` B 01 ` Z B s * H   <DMa QJ 8 72   <hQa T  74   <0Ta|@  75   <Wa @ ' 79   <[a 9`  76   <0]a Y` @ 74   <ga   75   <0ka YD@ 75   F 0  w #""F 0  a H Z(Ra ?? 0  n-1   @` G Z(^a ??  n-1   @` F Zpda ??  n-1   @` E Za ??  n-1   @` D Za ??  n-1   @` C Za ??   rparent   @` B Za ?? 0  b""  @` A Za ??   b""  @` @ Za ??   b""  @` ? Za ??   b""  @` > Za ??   b""  @` = Za ??    tdistance     @` < Z4a ??, 0   mF   @` ; Za ??,   mF   @` : Za ??,   mF   @` 9 Zi ??,   mF   @` 8 ZT i ??,   mF   @` 7 Zi ?? ,   rintree   @` 6 Za ??F 0 ,  mE   @` 5 ZH'i ??F ,  mD   @` 4 Z0i ??F ,  mC   @` 3 Z9i ??F ,  mB   @` 2 ZDCi ??F ,  mA   @` 1 ZLi ?? F ,  V  @`B I Zo ?? F 0 F B J T1 ?? , 0 , B K T1 ??  0  B L T1 ??  0 B M Zo ?? 0 B N Zo ?? F B O T1 ??F B P T1 ??F B Q T1 ??F B R T1 ??F B S T1 ??F B T Zo ??0 F 0 G F p@pP  x m } 2 y 0Qip0`  5a 2 z 0Ui ` P  5c 2 { 0XYi   5e 2 | 0D]iP @  5d 2 } 0@ai pp` 5b Z ~ s *=  SZ  s *@ = 8Z  s * x ` `  01= P 8`  01 s `  01  ` B 01 ` Z B s * H   <@gi QJ 8 72   <ki T  74   <oi|@  75   <@si @ ' 79   <vi 9`  76   <hzi Y` @ 74   <}i   75   <i YD@ 75 v  F 0  # #""F P w  Zi ?? 0  n-1   @`  Zi ??  n-1   @`  Zpi ??  n-1   @`  ZĨi ??  n-1   @`  Zi ??  n-1   @`  Zli ??   rparent   @`  Zti ?? 0  b""  @`  Z|i ??   b""  @`  Zi ??   b""  @`  Zi ??   b""  @`  Zdi ??   a0"  @`  Zi ??    tdistance     @` ¤ Z i ??, 0   mF   @` ä Zj ??,   mF   @` Ĥ Zj ??,   mF   @` Ť Z\j ??,   mF   @` Ƥ Zj ??,   mT   @` Ǥ ZP)j ?? ,   rintree   @` Ȥ Z+j ??F 0 ,  mE   @` ɤ Z@j ??F ,  mD   @` ʤ ZIj ??F ,  mC   @` ˤ ZRj ??F ,  mB   @` ̤ Z9j ??F ,  mA   @` ͤ ZUj ?? F ,  V  @`B Τ  `o ?? F 0 F B Ϥ Z1 ?? , 0 , B Ф Z1 ??  0  B Ѥ Z1 ??  0 B Ҥ  `o ?? 0 B Ӥ  `o ?? F B Ԥ Z1 ??F B դ Z1 ??F B ֤ Z1 ??F B פ Z1 ??F B ؤ Z1 ??F B ٤  `o ??0 F 0 H  0޽h ?     y}~|}yzy|z||{}{{z ̙330  0 00>y/(  ~  s *Di U  i G F p@pP   p00 2  05jp0`  5a 2  0` j ` P  5c 2  0\#j   5e 2  08jP @  5d 2  0i pp` 5b Z   s *=  SZ   s *@ = 8Z   s * x ` `   01= P 8`   01 s `  01  ` B 01 ` Z B s * H   <]j QJ 8 72   <Dj T  74   <j|@  75   <tj @ ' 79   <ĝj 9`  76   <j Y` @ 74   <j   75   <j YD@ 75   F 0  # #""F 0  j  Zȫj ?? 0  n-1   @`  Z4j ??  mA   @`  Zdj ??  mA   @`  Zj ??  mA   @`  Zhj ??  n-1   @`  Zj ??   rparent   @`   Zj ?? 0  b""  @` ! Zj ??   e2&  @` " ZDk ??   a5"  @` # Z k ??   o9"   @` $ Zk ??   a0"  @` % Z<k ??    tdistance     @` & Z$k ??, 0   mF   @` ' Z.k ??,   mF   @` ( ZH7k ??,   mF   @` ) Z@k ??,   mF   @` * ZIk ??,   mT   @` + ZDSk ?? ,   rintree   @` , Z\k ??F 0 ,  mE   @` - Z_k ??F ,  qD   @` . Zpk ??F ,  mC   @` / ZDzk ??F ,  mB   @` 0 Zk ??F ,  mA   @` 1 Zk ?? F ,  V  @`B 2 Zo ?? F 0 F B 3 T1 ?? , 0 , B 4 T1 ??  0  B 5 T1 ??  0 B 6 Zo ?? 0 B 7 Zo ?? F B 8 T1 ??F B 9 T1 ??F B : T1 ??F B ; T1 ??F B < T1 ??F B = Zo ??0 F 0 J y Tԕk ?? Y+ Le nSud de dpart est A. La table des distances et des parents est mise jour pour tous les nSuds adjacents A. On slectionne parmi les nSuds restants celui reli par l arte de plus petit poids.   H  0޽h ?      ̙33>1  0 00>?v/(  ~  s *jk U  k G F p@pP   p00 2  08kp0`  5a 2  0k ` P  5c 2  0j   5e 2  0^kP @  5d 2  0 Tl ?? Y+ "Le nSud de dpart est D. La table des distances et des parents est mise jour pour tous les nSuds adjacents D pas encore dans l arbre. On slectionne parmi les nSuds restants celui reli par l arte de plus petit poids (ici C et E possibles).  H  0޽h ?      ̙331  0 00 >>H/(  ~  s *l U  l G F p@pP   p00 2  0lp0`  5a 2  0l ` P  5c 2  0ol   5e 2  0p ??  n-1   @`  ZHp ??   rparent   @`   ZPp ?? 0  e4&  @` ! Z[p ??   a2"  @` " ZLdp ??   a4"  @` # Zmp ??   o6"   @` $ ZDwp ??   a0"  @` % Z|p ??    tdistance     @` & Z؊p ??, 0   mF   @` ' Z{p ??,   mT   @` ( ZXp ??,   mT   @` ) Z p ??,   mF   @` * Zp ??,   mT   @` + Zp ?? ,   rintree   @` , Zp ??F 0 ,  qE   @` - Zp ??F ,  mD   @` . Zp ??F ,  mC   @` / Zp ??F ,  mB   @` 0 Zp ??F ,  mA   @` 1 Z p ?? F ,  V  @`B 2 Zo ?? F 0 F B 3 T1 ?? , 0 , B 4 T1 ??  0  B 5 T1 ??  0 B 6 Zo ?? 0 B 7 Zo ?? F B 8 T1 ??F B 9 T1 ??F B : T1 ??F B ; T1 ??F B < T1 ??F B = Zo ??0 F 0 x > Tq ?? Y+ Le nSud de dpart est C. La table des distances et des parents est mise jour pour tous les nSuds adjacents C pas encore dans l arbre. On slectionne parmi les nSuds restants celui reli par l arte de plus petit poids.  H  0޽h ?      ̙331  0 000>>H/(  ~  s *p U  p G F p@pP   p00 2  0ppp0`  5a 2  0`p ` P  5c 2  0 q   5e 2  0"qP @  5d 2  0(q pp` 5b Z   s *=  SZ   s *@ = 8Z   s * x ` `   01= P 8`   01 s `  01  ` B 01 ` Z B s * H   <.q QJ 8 72   <1q T  74   <'q|@  75   <|;q @ ' 79   < 4q 9`  76   <@q Y` @ 74   <Dq   75   <9q YD@ 75   F 0  # #""F 0  q  Z0Lq ?? 0  mD   @`  Z :q ??  mA   @`  Z@Pq ??  mD   @`  Zqq ??  mE   @`  Zbq ??  n-1   @`  ZЄq ??   rparent   @`   Zq ?? 0  a4"  @` ! Zq ??   a2"  @` " Zq ??   a4"  @` # ZLq ??   s5&   @` $ Z8q ??   a0"  @` % Z@q ??    tdistance     @` & Zq ??, 0   mT   @` ' Zhq ??,   mT   @` ( ZXq ??,   mT   @` ) Zq ??,   mF   @` * Z T9s ?? Y+ Le nSud de dpart est E. La table des distances et des parents est mise jour pour tous les nSuds adjacents E pas encore dans l arbre. On slectionne parmi les nSuds restants celui reli par l arte de plus petit poids.  H  0޽h ?      ̙337=  0 <<@TTo:(  ~  s *Rs U  s G F p@pP   p00 2  0l^sp0`  5a 2  0q ` P  5c 2  0cs   5e 2  0gsP @  5d 2  0ks pp` 5b Z   s *=  SZ   s *@ = 8Z   s * x ` `   01= P 8`   01 s `  01  ` B 01 ` Z B s * H   <qs QJ 8 72   <tts T  74   <ss|@  75   <D{s @ ' 79   <q 9`  76   <}s Y` @ 74   <s   75   <Xs YD@ 75   F 0  # #""F 0  s  Z s ?? 0  mD   @`  ZLs ??  mA   @`  Zs ??  mD   @`  Zs ??  mE   @`  Z(s ??  n-1   @`  Z|s ??   rparent   @`   Zs ?? 0  a4"  @` ! Zs ??   a2"  @` " Zds ??   a4"  @` # Zs ??   o5"   @` $ Zs ??   a0"  @` % Zs ??    tdistance     @` & Zhs ??, 0   mT   @` ' Zt ??,   mT   @` ( Zt ??,   mT   @` ) Zt ??,   mT   @` * Z`#t ??,   mT   @` + Zh,t ?? ,   rintree   @` , Z5t ??F 0 ,  mE   @` - Z8?t ??F ,  mD   @` . ZHt ??F ,  mC   @` / ZQt ??F ,  mB   @` 0 Z4[t ??F ,  mA   @` 1 Zdt ?? F ,  V  @`B 2 Zo ?? F 0 F B 3 T1 ?? , 0 , B 4 T1 ??  0  B 5 T1 ??  0 B 6 Zo ?? 0 B 7 Zo ?? F B 8 T1 ??F B 9 T1 ??F B : T1 ??F B ; T1 ??F B < T1 ??F B = Zo ??0 F 0 X > Txjt ??  Plus rien ne change. La table parent nous fournit l arbre de couvrant minimum!N  G F  p   ? % ` `52 @ 0nt `P 5a 2 A 0Drt   5c 2 B 00vt@ 0  5e 2 C 0zt 5d 2 D 0}t0  5b Z E s * 0Z F s *mShZ G s * P( ` H 0p -h` I 0p}# ` J 0pc# ` KB 0p Z LB s *x @  M <t6h 72  N <؇t@ 74  O <t,   75  P <tpPW 79  Q <(tLiP 76  R <tLp 74  S <Pt P  75  T <t0p 75 H  0޽h ?      @DE CDF @AG @CH ACICBJDBKBAL ̙33  0 P(  r  S t U  t r  S  t   t r  S s   t H  0޽h ? 333380___PPT10.Ȥ D$  0 $(  r  S t U  t r  S t   t H  0޽h ? 333380___PPT10.l $  0 `$(  r  S ( U  t r  S 8    H  0޽h ? 333380___PPT10.ߤ0X0  0 p0(  x  c $`t U  t x  c $t   t H  0޽h ? 333380___PPT10.ߤ0X0  0 0(  x  c $Lt U  t x  c $$t   t H  0޽h ? 333380___PPT10.ߤ0X 0  .3(  8 p@p 2]dN     N     2  6 vjJP O0a  2  6pvjJ@   Ha 2  6vjJ@ Ha 2  6PvjJ  Ha 2  6 vjJ  Ha lB   <DjJP   B"v@ O N10a  lB   <DjJp    B$v '  M5a      BC@DE(FjJ @ XX 0X@ @   0 lB  <DjJ    B*v= M2a     BpC@DE(FjJ @(Ph`pp`PP(X @   p lB  <DjJpplB  <DjJ @   B1v   M1a  lB  <DjJ p @p    BC@DE(FjJ @ XX 0X@ @     lB  <DjJ@     BpC@DE(FjJ @(Ph`pp`PP(X @   `p lB  <DjJ0`p  B4v  M3a    Bh6vM   M4a    B@v W  M2a    B01v M6a  N @   @ lB  <DjJ@ lB  <DjJ@    B:v   M9a   ! B`Iv ` o  M7a   " <JvpP/p Msa   # <Rv@` Mua   $ < Xvp@D` Mva   % <]vJ j  Mxa   & <\v0 tP  Mya  N u1  ' u1  ( TZL^v jJ? O8a   ) TZ_v jJ?[j O8a   * NZHlv jJ? 1  O8a   + TZ`ov jJ?f u1  O8a   1 Typ@D` Mva   " <XGyJ j  Mxa   # <4Ky0 tP  Mya  r * S My U  y H  0޽h ? ̙33y___PPT10Y+D=' = @B +  0  (  x  c $PQy U  y r  S Qy D~  y r  S Ry   y H  0޽h ? 333380___PPT10.ߤ0X  0 H@ <(  < < C x~ygֳgֳ ? U  y  < C xhygֳgֳ ?   y H < 0޽h ? ̙33*  0 (*(  (r ( S @y U  y x ( c $y   y H ( 0޽h ? 333380___PPT10.`7W 0 @""D:(  D D C xygֳgֳ ? U  y  D NA ??2m BX $0J0P8 t   "D 1 l2 D <1?t  ll2 D <1?i@l2 D <1?-gl2 D <1?b l2 D <1?Q rB  D B1?0prB  D B1?DrB  DB B1?)rB  D B1?@P@rB  DB B1?   D Tygֳgֳ?& Bv1$   D Tygֳgֳ?FZ& Bv2$   D T ygֳgֳ?*  Bv3$   D Tygֳgֳ?*  Bv4$   D Tygֳgֳ? P p Bv5$   D Tygֳgֳ?z 53  D Tİygֳgֳ? 52  D Tygֳgֳ?p  52 rB D B1?p` `  D Tygֳgֳ?   54  D Thygֳgֳ? 51  D Tygֳgֳ?f@:`  53 rB DB B1?  D Tygֳgֳ?6 51  D Tygֳgֳ?f: 59 rB D B1? rB DB B1?P `rB DB B1?    D Tygֳgֳ?v 6JV 53  !D Tygֳgֳ?Vjv 55 H D 0޽h ? ̙33  0 H@PH(  H H C x`ygֳgֳ ? U  y  H C x8ygֳgֳ ?   y H H 0޽h ? ̙33$  0 h$(  hr h S y U  y r h S y   y H h 0޽h ? 333380___PPT10.~  0 H@`L(  L L C x|ygֳgֳ ? U  y  L C x  t  BCDEXF(8pX@(N@82 T<h(4m#@       d T  t  fBCDEF<%% ."RDBt@ Hnfr~<bhN:2Lf DLT<Z|L@             -@  t T {1?)  lPlus court chemin utilisant les nSuds {V1, . . . Vk }l7 '     7 H t 0޽h ? ̙33(  0   xh (  x x C xt7{gֳgֳ ? U  {  x C xL8{gֳgֳ ?   { X2 x 0m k X2 x 0 / X2 x 0 "  x 0T({m g  RVi4   x 0D{   lVj4    x 0I{ ]  lVk4  Z  x  2B CDEdF,o3)1-1%{v4D|. * & , $<  Y 8 B@         I   x <O{  DtPlus court chemin utilisant les nSuds { V1, . . . Vk -1 }z; (    2&  ^B  x 6D@  >  x  BCDEXF(8pX@(N@82 T<h(4m#@         m  x  fBCDEF<%% ."RDBt@ Hnfr~<bhN:2Lf DLT<Z|L@             /   x  `l\{1?S  nPlus court chemin utilisant les nSuds {V1, . . . Vk }`8 (    (&  H x 0޽h ? ̙33&  0 &&p47%(  ~  s *p{ U  { V8  0 6     `r{1? L  RW = D0 =.    N ` 0  ` 0N  @p  P   Zy{1? @` 74   Zf{1? @ ` 70   Zd|{1?@p` 75    Z{1? `  72    Zl{1? ` 70    Z{1?`p D&    ZL{1?   :    Z{1?  8-3   Z|{1?p 70    `{1? 0P 51    `{1?0P 52    `{1?0pP 53    `8{1?` 4 @ 51    `{1?` @4 ` 52    `Щ{1?` `4  53 88 P @  7c #  N ` 0  ` @ N  @p  P   Z{1? @` 70   Zl{1? @ ` 70   Z{1?@p` 70   Z{1? `  70   Z {1? ` 70   Z{1?`p C0&   Z{1?   90   Z{1?  70   Zx{1?p 70     `X{1? 0P 51  !  `<{1?0P 52  "  `{1?0pP 53  #  `{1?` 4 @ 51  $  `8{1?` @4 ` 52  %  `{1?` `4  53  &  `{1?P P p  7P = D8 p@  5G X 2 ' T{o?p 71 2 ( TD{o?p`   72 2 ) TD{o?P@ 73  * To?A +B To? b ,B  `GYH@WI'o?g0 b -  fGHIWo?)0  .  `0{1?6  55  /  `l}1?p0 P  6-3  0  `D}1?Fj 52  1  ` }1?:Z 54 H  0޽h ?O')*)(+(',('- ̙33  0 (JF(     `}1?  O D1 =.   F ` 0  ` ` N  @p  P   Z}1? @` 74   Z}1? @ ` 70   Z}1?@p` 75   Zp!}1? `  72    Zx}1? ` 70    Z#}1?`p C7&    Z8.}1?   :    Z2}1?  8-3    Z0}1?p 70    `:}1? 0P 51    `X9}1?0P 52    `A}1?0pP 53    `E}1?` 4 @ 51    `XI}1?` @4 ` 52    `L}1?` `4  53  F ` 0   ` pN  @p  P   ZP}1? @` 70   ZXO}1? @ ` 70   Z<=}1?@p` 70   Z\}1? `  70   Zd[}1? ` 70   ZW}1?`p C1&   Zc}1?   90   Zf}1?  70   Z8k}1?p 70    `o}1? 0P 51     `r}1?0P 52  !  `v}1?0pP 53  "  `hz}1?` 4 @ 51  #  `4~}1?` @4 ` 52  $  `}1?` `4  53  %  `̅}1?0 PP  7P = ~ 3 s *Ԍ} U  } ~ 4 s *}  wI }  J T} ??  \K = 1 Le nSud 1 peut tre nSud intermdiaire. .  H  0޽h ? ̙33h  0 (H(     `}1?  O D2 =.   F ` 0  ` ` N  @p  P   Zd}1? @` 74   Z}1? @ ` 70   Z}1?@p` 75   Z0}1? `  72    Zt}1? ` 70    Z}1?`p C7&    Z}1?   :-1    Z}1?  8-3    Z}1?p 70    `(}1? 0P 51    `}1?0P 52    `p}1?0pP 53    `P}1?` 4 @ 51    `4}1?` @4 ` 52    `}1?` `4  53  F ` 0   ` pN  @p  P   Z,}1? @` 70   Z}1? @ ` 70   Z}1?@p` 70   Z<}1? `  70   Z,}1? ` 70   Z}1?`p C1&   Zp}1?   92   Z$u1?  70   Zu1?p 70    `u1? 0P 51     `P u1?0P 52  !  `Hu1?0pP 53  "  `u1?` 4 @ 51  #  `u1?` @4 ` 52  $  `u1?` `4  53  %  `u1?0 PP  7P =  F # l#ugֳgֳ ? U  u ~ & s *!u  P v u 0 H T'u ??  tK = 2 Les nSuds 1 et 2 peuvent tre nSuds intermdiaires. :  H  0޽h ? ̙33j  0 (H(     `}1?  O D3 =.   F ` 0  ` ` N  @p  P   Z/u1? @` 72   Zp?u1? @ ` 70   ZL:u1?@p` 75   ZMu1? `  72    ZPu1? ` 70    ZTu1?`p C7&    ZYu1?   :-1    Z^u1?  8-3    Z0bu1?p 70    `_u1? 0P 51    `piu1?0P 52    `Hmu1?0pP 53    `ru1?` 4 @ 51    `\vu1?` @4 ` 52    `hzu1?` `4  53  F ` 0   ` pN  @p  P   ZRu1? @` 73   Z,u1? @ ` 70   Zsu1?@p` 70   Zu1? `  70   Zu1? ` 70   Zu1?`p C1&   Zu1?   92   Z$u1?  70   ZPu1?p 70    `Ԥu1? 0P 51     `Xu1?0P 52  !  `lu1?0pP 53  "  `u1?` 4 @ 51  #  `u1?` @4 ` 52  $  `pu1?` `4  53  %  `ľu1?0 PP  7P =  F # lugֳgֳ ? U  u ~ & s *8u  ] u 2 H Tu ??  vK = 3 Les nSuds 1, 2, 3 peuvent tre nSuds intermdiaires. ;  H  0޽h ? ̙33  0 <(  ~  s *u U  u ~  s *|u   u H  0޽h ? ̙330  0 00(  0x 0 c $u U  u x 0 c $u   u H 0 0޽h ? 333380___PPT10.`7W0  0 40(  4x 4 c $ U   x 4 c $    H 4 0޽h ? 333380___PPT10.`7W0  0 80(  8x 8 c $4 U   x 8 c $     H 8 0޽h ? 333380___PPT10.`7W0  0  0(  x  c $) U   x  c $*    H  0޽h ? 333380___PPT10.`7W$  0  $(  r  S  U   r  S `    H  0޽h ? 333380___PPT10.:$  0 $(  r  S ny U  y r  S \oy   y H  0޽h ? 333380___PPT10.ߤ@rs$  0 $(  r  S 0 U   r  S =    H  0޽h ? 333380___PPT10.ߤ@c$  0 $(  r  S M U   r  S lN    H  0޽h ? 333380___PPT10.ߤ@#0 s(  ^  S      c $,m @   i#Single Source Shortest Path Problem$$` $ H  0޽h ? ̙330 ,(  ^  S      c $݁SX?\ w~_xWG:OkMDdM:cXĀK8H@q(&N߄#[a >Tbm6[OO,,Z5vD(O/o0p.sd^u/1X4l2^1K$KYL@ ì_ #)nyHf ̣|J [ aT{1W]ڠѠxI)EރĊ;I'_iJe鋋R܇RV|$$!c4d&$!O|5Ю5n [AI;5D/@ wRH/ z uI9 RCRZҖ!ܸԣa\H)%sjPE?qk[N:oGf JUT JHp=n! ԝN gN73sP"\_s:#s{l'!3?)UlNbQƘiF<*KU1Oh+'0pUL \h    Module 1 : ComplexitPierre MouselXMacintosh HD:Applications:Microsoft Office 2004:Templates:Presentations:Designs:BlendsNino69Microsoft PowerPoint@w@@S@g@񟛍|GSg  )'    """)))UUUMMMBBB999|PP3f333f3333f3ffffff3f̙3ff333f333333333f33333333f33f3ff3f3f3f3333f33̙33333f333333f3333f3ffffff3f33ff3f3f3f3fff3ffffffffff3ffff̙fff3fffff3fff333f3f3ff3ff33f̙̙3̙ff̙̙̙3f̙3f333f3333f3ffffff3f̙3f3f3f333f3333f3ffffff3f̙3f3ffffffffff!___www4'A x(xKʦ """)))UUUMMMBBB999|PP3f3333f333ff3fffff3f3f̙f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙33333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffff3fffffff3f̙ffff3ff333f3ff33fff33f3ff̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3ffffffffff!___www8888C88Yz888888zýCCCCCCCCCCCCCCCCmCmCmCmCmCmmmCmmmmmmmmmmmmmmmm88zz8C88Yz888zý8C88YzýG88zzGGCݼCCCC՜.+,D՜.+,   $, 4 -On-screen Show-T*- 4Arial WingdingsTimes New Roman宋体SymbolBlendsMicrosoft Equation 3.0#Module 5 : Algorithmes de graphesPlan du moduleArbre couvrant minimumArbre couvrant minimumArbre couvrant minimum Arbre couvrant minimumArbre couvrant minimum Arbre couvrant minimum Arbre couvrant minimum Arbre couvrant minimum Arbre couvrant minimum Arbre couvrant minimum Arbre couvrant minimum!Algorithmes de plus court cheminAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de DijkstraAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydAlgorithme de FloydProblème 10034Problème 10034Problème 10034  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles-P :B_PID_LINKBASEA_:0NinoNino  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !#$%&'()0Root EntrydO)Pictures Current User"SummaryInformation(UPowerPoint Document(^DocumentSummaryInformation8