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 :

parcours de graphe

Évaluations restantes : 5/5

.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