4) Le plus court chemin
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
Compléter le script ci-dessous :
Graphe du test :
.128013 l(9 _4:=vm26!-uS8w.s3/]+fr7g}ebh[pPicN05a,{onkyd1)t 050W0E0Z0P0K0b0u0e0L0b0P0u0u0i010Z0K0I010406050u0p0k0k0P0A0V040q0S0b0p0@0S0T050w0~1012140|0I04051k1d1n0w1k0|0W0K0j0,0.0:0=0.0T0C0p0P0C0E0o0I0V0Z0G1b0e0G0K0C0G0b1P0G0Z0`050%0F0b0E1w0/0;011O1Q1S1Q0Z1Y1!1W0Z0A1l1K0,170u0I0P0T0=0l011$1y010z0)0E0T0P0k0E1W1{1}221(251!282a0`0a0e0J0A0S0I0S0u0K1a0T0e0#1_0A0A0E0L2v1d2d0T1l0w1K2I1=1@1?1X0W2f1z0K0T272s1W1t1v0-1%2S2U0T0S2Y1W0I2B1l2G2I2/0}1|2w2!232(0A110b1W0P1N2B0z0=030f0f0L2)0E1S2%0S0o0N0o0X0`0e0X1d0P2:2?0{2=2e2^1(2`2|2~300E32013436383a2V3d0o20040e0l3k3m1}3o2G2R013t0P2}1l2 0G313335370#3D2(3F0v3h0v3L2F3n0|3P3r0=3S3U053W3Y3z3!3C2T3E3e0g3h0g3-1e3/3p2@1x3s0S2{3T3v3X3x3Z3B3$3 3(3e0O3h0O452/3:2?3Q3@4f3{3A3#394l3c3e0m3h0m4r473;4a3?4c3u3V3w3y4z3~3b3F0B3h0B4I3N4t3q4L3R4N4e4P4g4R3}4k4U3e0r3h0r4Z2H4#492#4(4d3^3`4h3|4j4B4:0o0d3h0d4^3O4u3=4}4O3_4Q4i4A3%4D3f0N0`0X0N5a4`4v4)4 5h525j4C3F0X3g045B5r485t4~4x514S4/403f3H0X3K0w3l3.4!5G5d4w4+4y4.545N0X3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602_5u5J645y550X4F5D4H6b4s5/616g5Z5K5#663e0X4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3f575D596Q5 6S6f6U6I6v6K550l5n046:5a1o2-1d2Y2L0W1@2Q5d4A2X1u1l2,0E2.3n5~1l4A772e0K0W0=352G5A3v7e7g6.5%212j0E7m6j7o2I5T6e1(0U0`0#0z796r230s3h7D7x3?0z0`2B0L0G0E0A7O0E367P0k2T7I6)1(0_040c7Y4$610`0C0A0P0I7P7(4{237#0Q790e7E3s7A0E1|0A0Z7;3Q7@7_7{3?0`120A1u0E0E825d7#0Y0h7_0e0e0|6c2H5G7l017h2?3F3H5g8q6w6L3G7p297r8r7n6Y8v5,8k8k863R0`7 270Z0u857J010S0`0i8S7Z0=7#0R8e5:7}7 818n7c7=7!0`8i8,7`8T0U0L0`0M1b8d8,8L7#0D798m2;3P8x0f7i3e5)8w7f8E7t6Y3*0e7q7s6X5l9a8I8J8L0T0`2h8}2/8?8Z8U8W8Y7)7?0`0H8%7*040#8*9E9B040x928296980o5`9b9j5M6Y429h8C9U5$9W1W9n8K8@0`0s1O1!9z8.87049s9/3Q8V040n8X8=8 9C0x8;6q8~959c8s1}3F689T9d9ka88B2a9!6x0oa99(8J9)9w9q040u0S100$9@5d9_9|9u9p9r269J1(9_0taC9;2r0IaG017#7%a39w7W0`5qaO9A8/040Y9NaT2w9P8t4E7ka58F5l4F9Yafab9Va+9%3lalal8L7z040K7C9}8Taoaqas8+ay8Tawax3n9vaU9;898b9t788T7#a147aZ0ea#a73e6Aaa8y554Wa-8Dbr5Nbpaka@9o9*042B0Z0p0A1ca~an7M0E0k1b0Z7T7S7WbI949waMaKao9H12b3bfbV0`7^bJba8M04bc0j8caK84b*9:b,8O0T8Qb;0`aX8=93b$7da)9Q6Nbqa*3F4=buag8zc5bzbB9wa`0z4cau8(040j0S0K2tbTb88L0S7Ga{cr3Nb9b@ao7,7.7:bk8f9CbX0`b12ab#3N9~9Lbi5Vbkbm0T3F6!c69e5l57caa/9#cZa=3IbAa@a_0`a|ck9Fcncp7Xb?9^cv2(cM2Hczc_c.cxc}az04b_b{cF4%bhaYbUc27m9Q5pa(cb6k5nc#bw6Ydf7vc*c+c+d39?d74|aEcIb-0I0I270Wb|7$dxc=cqdDb~9uc0cNa4dda$3f5CcXac6y3gdkc7dUc)dqdqd3d58Rdu9K9Dd)7|cmcodHd,8!0`9Mc^av9yd^clcKat8,dL8odN8Ede8v2 96cY5A20dWe86y8Ha?cfb+a`bEbGd13IcO0Hd@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`b7cyd3bZ80dDfa3ofcdOeJ0Xc5f=f`5Ac9f_eSglf}a^a frb2fu0=awgzb^f4b`f6c1b@7#f#gH4vgxfte#7#f,cRf.fE6ycWgngsc!greO0XcWcefQfq04fTelf~4%gBg3d*dxg5dDgRd2g80ygCaog,dagLf/3e6:ewgoh3djg!eBh4dogvcgbLbFbHg}fSe,eleF1d7b6^766`731d0Z6}ht2O2J0P1Zhq0w6{8m0#0%0)0u04.
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. Crédits
Romain Janvier, Gilles Lassus, Eduscol, Nicolas Revéret
# Tests(insensible Ă la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)