Les chemins
I. Le plus court chemin
Note
🤔 Comment est-on sûr qu'un chemin va être trouvé entre deux sommets A et B ?
Si le graphe est connexe, tout parcours en largeur au départ de A va parcourir l'intégralité du graphe, et donc passera par B à un moment.
Un chemin sera donc forcément trouvé entre A et B.
🤔 Comment est-on sûr que ce chemin trouvé est le plus court ?
Dans un parcours en largeur, on visite d’abord le sommet origine, puis la génération des sommets qui sont à distance 1 (en nombre
d’arêtes), puis la génération des sommets qui sont à distance 2, etc. Quant on visite le point d’arrivée, le numéro de sa génération
représente le nombre d’arêtes qui le séparent du point de départ.
Autrement dit, un parcours en largeur à partir du sommet d’origine permet de trouver un plus court chemin vers le sommet d’arrivée
en nombre d’étapes (c’est-à-dire d’arêtes traversées).
Si on prend la précaution de noter (dans un dictionnaire parents) le père de chaque génération de sommets, il suffit de remonter de
père en père pour reconstituer le chemin d’accès du point d’arrivée.
À vous de jouer 1
Compléter le script ci-dessous :
Graphe du test :
.128013 =y3f24o,g7!spN]v_ 56rb9:lSc[8auP{/.+kietwn-h(d}1m0) 050U0N0O0E0M0z0m0s0B0z0E0m0m0b010O0M0n010406050m0F0X0X0E0v0c040A0h0z0F0@0h0Q050I0~1012140|0n04051k1d1n0I1k0|0U0M0q0,0.0:0=0.0Q0j0F0E0j0N0R0n0c0O0S1b0s0S0M0j0S0z1P0S0O0`050%0w0z0N1w0/0;011O1Q1S1Q0O1Y1!1W0O0v1l1K0,170m0n0E0Q0=0f011$1y010e0)0N0Q0E0X0N1W1{1}221(251!282a0`0a0s0G0v0h0n0h0m0M1a0Q0s0#1_0v0v0N0B2v1d2d0Q1l0I1K2I1=1@1?1X0U2f1z0M0Q272s1W1t1v0-1%2S2U0Q0h2Y1W0n2B1l2G2I2/0}1|2w2!232(0v110z1W0E1N2B0e0=030r0r0B2)0N1S2%0h0R0Y0R0W0`0s0W1d0E2:2?0{2=2e2^1(2`2|2~300N32013436383a2V3d0R20040s0f3k3m1}3o2G2R013t0E2}1l2 0S313335370#3D2(3F0d3h0d3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0g3h0g3-1e3/3p2@1x3s0h2{3T3v3X3x3Z3B3$3 3(3e0t3h0t452/3:2?3Q3@4f3{3A3#394l3c3e0u3h0u4r473;4a3?4c3u3V3w3y4z3~3b3F0k3h0k4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0D3h0D4Z2H4#492#4(4d3^3`4h3|4j4B4:0R0x3h0x4^3O4u3=4}4O3_4Q4i4A3%4D3f0Y0`0W0Y5a4`4v4)4 5h525j4C3F0W3g045B5r485t4~4x514S4/403f3H0W3K0I3l3.4!5G5d4w4+4y4.545N0W3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550W4F5D4H6b4s5/616g5Z5K5#663e0W4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3f575D596Q5 6S6f6U6I6v6K550f5n046:5a1o2-1d2Y2L0U1@2Q5d4A2X1u1l2,0N2.3n5~1l4A772e0M0U0=352G5A3v7e7g6.5%212j0N7m6j7o2I5T6e1(0L0`0#0e796r230P3h7D7x3?0e0`2B0B0S0N0v7O0N367P0X2T7I6)1(0_040T7Y4$610`0j0v0E0n7P7(4{237#0i790s7E3s7A0N1|0v0O7;3Q7@7_7{3?0`120v1u0N0N825d7#0Z0y7_0s0s0|6c2H5G7l017h2?3F3H5g8q6w6L3G7p297r8r7n6Y8v5,8k8k863R0`7 270O0m857J010h0`0b8S7Z0=7#0H8e5:7}7 818n7c7=7!0`8i8,7`8T0L0B0`0o1b8d8,8L7#0V798m2;3P8x0r7i3e5)8w7f8E7t6Y3*0s7q7s6X5l9a8I8J8L0Q0`2h8}2/8?8Z8U8W8Y7)7?0`0C8%7*040#8*9E9B040p928296980R5`9b9j5M6Y429h8C9U5$9W1W9n8K8@0`0P1O1!9z8.87049s9/3Q8V040l8X8=8 9C0p8;6q8~959c8s1}3F689T9d9ka88B2a9!6x0Ra99(8J9)9w9q040m0h100$9@5d9_9|9u9p9r269J1(9_0JaC9;2r0naG017#7%a39w7W0`5qaO9A8/040Z9NaT2w9P8t4E7ka58F5l4F9Yafab9Va+9%3lalal8L7z040M7C9}8Taoaqas8+ay8Tawax3n9vaU9;898b9t788T7#a147aZ0sa#a73e6Aaa8y554Wa-8Dbr5Nbpaka@9o9*042B0O0F0v1ca~an7M0N0X1b0O7T7S7WbI949waMaKao9H12b3bfbV0`7^bJba8M04bc0q8caK84b*9:b,8O0Q8Qb;0`aX8=93b$7da)9Q6Nbqa*3F4=buag8zc5bzbB9wa`0e4cau8(040q0h0M2tbTb88L0h7Ga{cr3Nb9b@ao7,7.7:bk8f9CbX0`b12ab#3N9~9Lbi5Vbkbm0Q3F6!c69e5l57caa/9#cZa=3IbAa@a_0`a|ck9Fcncp7Xb?9^cv2(cM2Hczc_c.cxc}az04b_b{cF4%bhaYbUc27m9Q5pa(cb6k5nc#bw6Ydf7vc*c+c+d39?d74|aEcIb-0n0n270Ub|7$dxc=cqdDb~9uc0cNa4dda$3f5CcXac6y3gdkc7dUc)dqdqd3d58Rdu9K9Dd)7|cmcodHd,8!0`9Mc^av9yd^clcKat8,dL8odN8Ede8v2 96cY5A20dWe86y8Ha?cfb+a`bEbGd13IcO0Cd@a2dba!c3dP5(dgc$ahevebdT3f9m3le08-bletbn3f9Se6a)eceKaebvdXePdoc-9G3xaKcv7`d;3R7LbDbMbObQ7Vc@er830`aNe.5X8)b!dDb)b4bKb-2Abde_c:2_8N128Pd(e=d8b}cQ5.cSeIcU6ya9eMdh5%4oeAa:67dZegcAcJarcLf1aDd`e{b+aob.b:d 9Ofd5A6mdSfm6ya,9iex8z6lfoamfy0`bRe-csb5fwfVb%04d+f79FfAbedMfZepbje.cT5AbpfhfM6kbtfLdl5l6zfPc~5da`9,aBd{9Fd}c|emfW9`b7cyd3bZ80dDfa3ofcdOeJ0Wc5f=f`5Ac9f_eSglf}a^a frb2fu0=awgzb^f4b`f6c1b@7#f#gH4vgxfte#7#f,cRf.fE6ycWgngsc!greO0WcWcefQfq04fTelf~4%gBg3d*dxg5dDgRd2g80KgCaog,dagLf/3e6:ewgoh3djg!eBh4dogvcgbLbFbHg}fSe,eleF1d7b6^766`731d0O6}ht2O2J0E1Zhq0I6{8m0#0%0)0m04.
À vous de jouer 2
Nous allons utiliser une seule fonction. Au lieu d'un dictionnaire parents qui à chaque sommet associe son "parent", nous allons utiliser un dictionnaire dict_chemins qui à chaque sommet associe la liste représentant le chemin parcouru pour aller de depart à ce sommet.
Graphe du test :
Dans cet exemple, si on cherche le plus court chemin entre A et G, on obtiendra à la fin de l'exécution de l'algorithme :
dict_chemins = {'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'C'], 'D': ['A', 'B', 'D'], 'E': ['A', 'B', 'E'], 'F': ['A', 'B', 'E', 'F'],
'G': ['A', 'B', 'E', 'G']}
Ce dictionnaire permet de conserver les chemins complets depuis le départ, au lieu de juste noter le "parent".
.128013 =y3f24o,g7!sp]v_ 56rb9:lSc[8auP{/.+kietwn-h(d}1m0) 050T0M0N0D0L0y0m0r0A0y0D0m0m0b010N0L0n010406050m0E0W0W0D0u0c040z0h0y0E0?0h0P050H0}0 11130{0n04051j1c1m0H1j0{0T0L0p0+0-0/0;0-0P0j0E0D0j0M0Q0n0c0N0R1a0r0R0L0j0R0y1O0R0N0_050$0v0y0M1v0.0:011N1P1R1P0N1X1Z1V0N0u1k1J0+160m0n0D0P0;0f011#1x010e0(0M0P0D0W0M1V1`1|211%241Z27290_0a0r0F0u0h0n0h0m0L190P0r0!1^0u0u0M0A2u1c2c0P1k0H1J2H1;1?1=1W0T2e1y0L0P262r1V1s1u0,1$2R2T0P0h2X1V0n2A1k2F2H2.0|1{2v2Z222%0u100y1V0D1M2A0e0;030q0q0A2(0M1R2$0h0Q0V3c0_0r0V1c0D2/2=0`2;2d2@1%2_2{2}2 0M3101333537392U3c0Q1 040r0f3i3k1|3m2F2Q013r0D2|1k2~0R303234360!3B2%3D0d3f0d3J2E3l0{3N3p0;3Q3S053U3W3x3Y3A2S3C3d0g3f0g3+1d3-3n2?1w3q0h2`3R3t3V3v3X3z3!3}3$3d0s3f0s432.3.2=3O3=4d3_3y3Z384j3b3d0t3f0t4p453/483;4a3s3T3u3w4x3|3a3D0k3f0k4G3L4r3o4J3P4L4c4N4e4P3{4i4S3d0C3f0C4X2G4Z472!4$4b3?3^4f3`4h4z4.0Q0w3f0w4?3M4s3:4{4M3@4O4g4y3#4B3c0X0_0V0X584^4t4%4}5f505h4A3D0V0V5m3h0H3j3,4Y465r4|4v4 4Q4-3~3c3F0V3I5D3K2G1n2,1c2X2K0T1?2P5b4y2W1t1k2+0M2-3l5F5V4y5/2d0L0T0;342F5y3t5_5{515i5~0r2i0M615w535A2H5E4I4`0K0_0!0e5;5@4_220O3f6k5H5b0P0e0_2A0A0R0M0u6x0M356y0W2S0q0p5S2:6e220^040S6q6L3q0_0j0u0D0n6y6Q5a4#6N0i6k0r6r4#0P6h0M1{0u0N6Z4!4`6$6(6*4`6,04110u1t0M0M6=6m1%6N0Y0x6k0{443L5H60015|2=3D3F5e7e4,525O1 6528677f625x3d7j5T0r7z6)6R3;6h0L2C6D0M6F0P0m6_7C010h0_0b7M6!6@0_0G734t6-6/6;7b5V7N6N787$3G6`6M0_0B7X6s7Z117#6K7T7.040o0U797X7l0q5}3d3(4N81695O3(7q29684R891V7y7A7-6S042g727+7B7`1%7P047R8o8j0;6N7:7+8w3P7?6:7;6#0_0o7 8A3N81830Q40865`7t884k8O20668d5N8U8P3J7A8p6?226g040O1N1Z7S8)8k8m8:740;8s0l8u2.8(8^018y0o7*4q808R7g1|3D4m8Q8Y7n8U4m8b7s7m634l8g3j8%8%8B6|0m0h0 0#8@3O8s8|3l8~7Y8l258F4`8s0I9E2^0_2q0n9I750_6P8K8q0;6F0_5o9R8;8x0_0Y8J7_5^96827h4C5 9)8T5j4D9g9c9j0Q4D6c3G9n7z8B8+0L6j8v7N9q9s297^9z8B9x9y3L9A7=6}2z708n9%8 7)9$5:8L9)8N4U9b8S8e8U4U9=at8Z5jar8$9|9n9~6v0#0E0u1ba29S8C041s7G6B7J7L9Xak7/9N7D049r9ta77c7(8Hama%4s8M9+0Q4:as9i7va/8W7r9?a?a:aC9|aF8l4a9vae0p0h0L2saK8}a96o042Sb26+6T6V6XaianaM8yaXaNa!a6bn6N92a*7%a,apa.55a;7u5355axa=bC9l9{aD8i7N9 a1b9a30_b4b6bdaL9Y7Obb2%a$2Gad4#0hbbbTbOaM6|aP0N7HaSbr0_9345aU0ra-983d5n9-a`6a5lbEbB5Ob}9`bJbJ9p0_8?b^5b9Gbn6|6W0n260Tb;6OcfbQb5b7cl9#8o7aajb_bxb{3c6b7k9.au5j5za^8cay9dcEcA8hc7aEbPaO7Fb.aR2SaTcv5bbmccbf04bRcqcZ7U7|be9F7Qc+9JcQaQ6EcUcl8zcWc!bp9uc(7{8IbU8 8s0Jc.9O04c^bkbV6|c$b)d8aVc*7+cuddcw618N5Rb~cI9@dmc29/5y7x9mbKaM8+2A0NaIb8a8a(d6c 948A0H5?5W5.5Y5+1c0N5#dP2N2I0D1YdM0H5Z7a0!0$0(0m04.
À vous de jouer 3
Graphe du test :
Comme nous l'avons déjà vu pour le parcours en largeur, nous pouvons simuler une file en utilisant une liste visites, et un indice qui sert à pointer la valeur "défilée".
Compléter le script ci-dessous :
.128013 =y3f24o,êg7qsp]v_ 56rb9:lSc[8;auP{/.+kietwn-h(d}1m0é) 050V0O0P0F0N0z0n0s0B0z0F0n0n0b010P0N0o010406050n0G0Y0Y0F0v0c040A0h0z0G0_0h0R050J101214160~0o04051m1f1p0J1m0~0V0N0q0.0:0=0@0:0R0k0G0F0k0O0S0o0c0P0T1d0s0T0N0k0T0z1R0T0P0|050)0w0z0O1y0;0?011Q1S1U1S0P1!1$1Y0P0v1n1M0.190n0o0F0R0@0f011(1A010e0+0O0R0F0Y0O1Y1}1 241*271$2a2c0|0a0s0H0v0h0o0h0n0N1c0R0s0%1{0v0v0O0B2x1f2f0R1n0J1M2K1@1_1^1Z0V2h1B0N0R292u1Y1v1x0/1)2U2W0R0h2!1Y0o2D1n2I2K2;0 1~2y2$252*0v130z1Y0F1P2D0e0@030r0r0B2+0O1U2)0h0S0f0S0X0|0s0X1f0F2=2^0}2@2g2`1*2|2~30320O340136383a3c2X3f3f3j0f3m3o1 3q2I2T013v0F2 1n310T333537390%3F2*3H0d3j0d3L2H3p0~3P3t0@3S3U053W3Y3B3!3E2V3G3g0g3j0g3-1g3/3r2_1z3u0h2}3T3x3X3z3Z3D3$3 3(3g0t3j0t452;3:2^3Q3@4f3{3C3#3b4l3e3g0u3j0u4r473;4a3?4c3w3V3y3A4z3~3d3H0l3j0l4I3N4t3s4L3R4N4e4P4g4R3}4k4U3g0D3j0D4Z2J4#492%4(4d3^3`4h3|4j4B4:0S0x3j0x4^3O4u3=4}4O3_4Q4i4A3%4D3h0Z0|0X0Z5a4`4v4)4 5h525j4C3H0X3i045B5r485t4~4x514S4/403h225D3K0J3n3.4!5G5d4w4+4y4.545N0X3*5D3,5S3M2J1q2/1f2!2N0V1_2S5d4A2Z1w1n2.0O2:3p5U5.4A612g0N0V0@372I5A3x686a535k6d0s2l0O6g5y555C3-4K4|0M0|0%0e63664{250Q3j6y5W4%0R0e0|2D0B0T0O0v6L0O386M0Y2V0r0q5+2?6s250{040U6E6Z3u0|0k0v0F0o6M6(5c4%6#0i6y0s6F4|0R6v0O1~0v0P6;4$4|6@6_6{2{0|140v1w0O0O736A1*6#0#0y6y0~463N5G6f016b2^3H5P5g7r5#6i3g226k2b6m7s6h5z7B1Y5,0s7M6`6)3?0|0q0N2v0P0O0n777P010h0|0b7Y6=750|0C7g4v6~70727o5.7Z6#0p6_7O7)250B5C030s0G2W0s2j7f7=3q877q697G6c3g5)7x8b7z7I0S3*7D2c6n4T5N8f7L7N786*041v2F6R0O6T0R7X877{74257#047%8E8u0@6#0I7-5X7/147;6Y7|7i0|7l8L7@7+8Q6G8S718%7*040p0W7m7-7y0r8d0S424P8=6o5N428m7F8i558_3L7N8F7h7Q040N7(8G1*8I8K2;963Q6T0|5q8E9h5`7 0s2V8x1%2A0z02030d0x0E0!0z0!2c0R0P2z1%0P0j7V0s2t0G0v0s1$2z0!859E8U47893P8=8@4o8`8h7H554o8 8o5M4m0S9$948t7Z6u040Q1Q1$9b973R0|9a8!8W0@8I020z0P0E9}4v0w0|2k8+6!0|6%9Ya39 047S7U7Waf8X047k7`8M017~0|801O0o0O1b9S859P0)9F0s0m0G1%0N0sa6a89Q290Uan2w7W0#8:aj679(8@4F9%9-5$9/4F9,7G8|a+7K3n9595av9^0N6xa29c98aU7V8D8Va}016#7,aZ9~6}99aq8N0|7_a|9~9e9f3p9n8(047b7d86b29~6#8Z4s8;a#7u3g4Wa(a.8p9/4Wa-915Nbz9=a?a?a^6J0(9O1ebf7.8w0N8y6P8Bb1628#04b6bqbSa apb73Qb5bbala1b%5d7^bebub+9!bx0S4=bAbG9/4=bF9)5Nb}bJbL9@0|0e4caa8Ram0h7T2Vcc4%0h6C99bQ9gavb96,6.6:b+b=8$cublb)bY7pb!b$bZakb9b:cEb3b?btbjbk4|ax04az2y02aK0ha80V9T28cT0GcV0E0scz0C0N0p0s0(0s1O2D0k142A0n7Wc(cf2v8CaYb%b`1 3H57b~c39/57c2a/5ld3c6bK7MbM99a{co7Zb90qc{chbR5dck0|2*9W3NcN8HcldndicF6vbU0P8zbXb.bsc~cI2yd00R5A5nd4d9dN236la)7A5ma;04dddZdv8vczb.8I0Kb.b96.aB0R0VdGahd+7RdmcndJb,0|aX9mavcPcRc-6H28dIcB4udL5A6q318{bC5l5BdS7EdU8jef2Ka=d!bKcpdBbV6S2VcA7?akb-cx6|d@cgd_e6cJbdci4|9eeG79bTer8Aetd;b#d?amcgb0ePcDeDb8a0eP0pb@bjav8I0LeJareWevb3dkd^e!e5e.dKbwd13g0X7web9(dQe{7CdTbB9.ee7w8seodjeZdocj7$e+98cHdue(0|e*fc4|9j5D7`7nc e_dMe{8fe~ei6p8lf3b ee8remdec8042D0PbPffb47+e$5V890J655/605;5}1f0P5@fY2Q2L0F1#fV0J5=7n0%0)0+0n04.
II. Remarques
Retour sur l'efficacité
-
Pour une question de simplification des codes, Nous avons utilisé ma_liste.pop(0).
👉 Pour pallier à ce problème, nous pouvons utiliser le deque du module collections
documentation deque
-
Nous avons aussi utilisé une concaténation de liste à gauche. C'est également très coûteux, à cause de tous les décalages
qu'il faut effectuer dans la liste à chaque fois qu'on ajoute un élément à gauche.
👉 il vaut mieux créer la TAD file avec une liste chaînée compléments TAD
III. Exercices
Exerice 1:
Chemin dans un réseau
Exercice 2 :
La rumeur qui court
IV. Crédits
Romain Janvier, Gilles Lassus, Eduscol, Nicolas Revéret
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)