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 :
.1280130ldy1,4{]k/we!ibmc_:35}aPr+ 7=9o[f.gt286sSh)(pNunv050d0n0L0y0p0c0P0C0s0c0y0P0P0E010L0p0U010406050P0W0r0r0y0A0e040Q0G0c0W0?0G0X050l0}0 11130{0U04051j1c1m0l1j0{0d0p0Y0+0-0/0;0R0p0K0R0c1A0R0L0_050$0q0c0n1v0.0:011z1B1D1B0L1J1L1H0L0A1k0L0R0+160P0U0y0X0;0M011N1x010I0(0n0X0y0r0n1H1*1,1;1P1@1L1`1|0_0a0C0z0A0G0U0G0P0p190X0C0!1(0A0A0n0s2h1c1 0X1k0l1$2u1Z1#1!1I0d210;1D0X1_2e1H1s1u0,1O2E0p2G0X0G2K1H0U2n1k2s2u2Y0|1+2i2M1=2R0A100c0_0C0f2r2$0`2#202(1P2*2,2.0M2;1,2?2s2D012{0y2-040C0v2 2t0{322_0;35370C0h3b312$333h2.0w3l3d3n3f340G2+362.0O3s2@2%1w2`3x2|380D3C3e3F3g3H3z380N3L3u3N3w3y3i0F3T2^3V3p040f0b3!3E2N3W3I0f2:1d2=3t3#3-3%0f2~3=303@3,2)3P370f3a3}3c3D3o420_0f3k463m3^413X4b3r4e3 494i3(3B4l483v3`3K4r3M3_4a3(3S4w3U4y4o0f3Z4C4g3G4o0M3*4e1n2W1c2K2x0d1#2C3v0s2S1}1k4S1l4Q2!4O4Y0!2X4D1=0k0_0!0I3l0C4s3$0I0_2n0s0R0n0A4~0n0t520r2P3l4_3-0^040T584x2)0_0K0A0y0U4 5e4.1P5b0g4@595g040!1+0A0L5n4J0;5q5s5f2`0_110A1t0n0n5A405p0_0S0u4@0C0C065U5U5t5G045x1_0L0P5E5o0;0G0_0E5*5B015b0i5N3o4;0n5x5z4O5F5C0_5S4e4^5 010k0s0_0V1a5M5~5+5=0_0x3s5X646e0X0_236c2Y6k5;5-045/635Z60040H5^4t5`5|6B3V5b0j6i5X6x660_0m1z1L5:5O3g6n1^6R336t0o6v6q6L5b0H0j622Y5W6j6K656m040P0G0 0#6W3v6t6!2=6r6S346U6Q6d6s0_0J6F3_0_2d0U771=5b5d736 560_4N2!655b0S6J6-6~334:040p4?6w6/0_6=6@5}6#656{6|307r6C045I5K6p2=6$617p7q6.6e7t2n0L0W0A1b7x6l4|0n0r1a0L5355577g337e7c5!5w117C7O7m0_5r7#5;6:7L0Y5L7=6y7}7D7$5#115%5)7/3v7n4@6,7q6L7t0I3x6_3$0_0Y0G0p2f7!876s0m0_7.8v6 6:5i5k5m8d6G0_6A8G786;6?1|7_307P046)7R7S7I3V7t7v8n8L8q8s8z6}6L0G8x042R8P2t8W3-8+8y8u8)7y892n0X5(846f046*3?8V8V6L6:6o8 6t768K5u5k0U1_0d8 7;9c5!8$8t9i5Q8g947S96798a8}8c7l6e6%8 6:9m8(8Q7{8S8!1=6{9I5!7A8O7R8j7%7X7Z9L6y6(3s4m3v7t4=9U344{042n7)8}7,4 568^9F9z0_7f9y7 6D7^9o04868_8881839k859$6:5$9w9|5R9P8`9N6^7~6 9Kaf5_7K2m7Mab887-9:8:8*5.9$9Aa370ak5J827N9;5;6Han5;7t6O6Vai7Jad8/38as046Za59`5y9|923~95ac8Nae8A6XataK8o8{8b9|8J9^8B7za!aN8R6I4laYao9.9Ear7Ea(a$8e8I9Ba;7B9|a^b13V6t0BaS04apaF6 7V0#7YaqaO8`bf4r0l4+0n2u2Vbs4R1t4T2x2A2v0y1Kbv0l4S0{bF0#0%0)04.
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)
(Ctrl+Clic pour inverser les colonnes)