Aller au contenu

Recherche de chemins⚓︎

Conventions pour cette partie

Dans les exercices suivants, nous utiliserons pour représenter les graphes des dictionnaires associant les sommets avec la liste de leurs voisins.

Pour les parcours en largeur, nous utiliserons des algorithmes itératifs.

Pour les parcours en profondeurs, nous utiliserons des algorithmes récursifs, la pile d'appel remplaçant la pile de la version itérative.

Les fonctions sur les files et piles sont déjà définies.

Les graphes suivants sont également déjà définis :

graphe1_dico = {
    0: [1, 2],
    1: [2],
    2: [0, 1],
    3: [1, 2]
    }


graphe2_dico = {
    0: [1, 2],
    1: [3],
    2: [8],
    3: [2, 4],
    4: [7],
    5: [0],
    6: [5],
    7: [5],
    8: [9],
    9: [2]
    }


graphe3_dico = {
    0: [1, 2, 3],
    1: [0, 3],
    2: [0, 3],
    3: [1]
    }


graphe4_dico = {
    0: [1, 3],
    1: [2],
    2: [7],
    3: [4],
    4: [6],
    5: [0],
    6: [2, 7],
    7: []
    }  


graphe5_dico = {
    0: [5, 7],
    1: [3],
    2: [0, 4],
    3: [2],
    4: [3],
    5: [],
    6: [5],
    7: [6]
    }
Exercice 9 : existence d'un chemin (parcours en largeur itératif)

Compléter le code de la fonction existe_chemin qui prend en paramètres un dictionnaire de listes de voisins graphe et deux sommets depart et arrivee, et qui renvoie un booléen indiquant s'il existe un chemin allant de depart à arrivee.

On fera un parcours en largeur utilisant une file d'attente.

Exemples
>>> existe_chemin(graphe1_dico, 0, 1)
True
>>> existe_chemin(graphe1_dico, 3, 0)
True
>>> existe_chemin(graphe1_dico, 2, 3)
False
>>> existe_chemin(graphe2_dico, 0, 9)
True
>>> existe_chemin(graphe2_dico, 6, 2)
True
>>> existe_chemin(graphe2_dico, 2, 1);
False
>>> existe_chemin(graphe2_dico, 4, 6)
False
Indication

L'algorithme fonctionne de la façon suivante :

  1. On marque tous les sommets à non vu et on place depart dans la file d'attente.
  2. Tant que la file n'est pas vide :
    1. On défile un sommet.
    2. On regarde si on est arrivé.
    3. On marque comme vus tous ses voisins non encore vus et on les mets dans la file d'attente.
    4. On marque le sommet courant comme traité.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013/1n5k9rw&_l:a"ugb 2,h6y.7x4pTif8So]};F){s=év[03t mde(qcP010R0S0O0f0w0d0H0k0V0d0f0H0H0I0g0O0w0u0g000P010H0h0Q0Q0f090p000z0A0d0h0/0A0501030_0{0}100@0R0w0K0k0|09070R0A0a050-040g0k0H0O0p0d0S0-1k0i0w050e040q0r0S0Q0k041J1t0?0X1h0'0)0+0-0n0w0i0n0d1X0n0O0=010!0j1y1S0*0,0g1W1Y1!1Y0O1(1y1&0O09001'0n0'130H0u0f1q0g0l1t0(1,0-0x0$0S050f0Q0S1&22241+1U0g2c1y2f2h0=020k0W090A0u0A0H0w16050k0Y2009090S0V2D192k051|030O0n2Q1`1|2V1'0R2m1-1!052e2A1&1g1i292n2$2&2)1&0u2J1|2O2Q2@0^232E2+1-050A090|0d0=1L2N2{1P2O2!0-30320f34000k0l3724392{3b0g3d33350N3k2P0@3a2}3c313r3h0t3u3m2l3y3p3A3f35063E3w3n3H3q3K3h0o3N2`3G1T2~3J3g0k0r3V3x3Y3z3e3#0y3&3P3(3I3*35083-3X2a3:3B040M3@2|3/3R3g04043~3o420=043j1a383O3^2n4800043t4c3l4e403_4h043D4l3v3W4o4g3!493M4t3F4w3Z3;4i3U4B192;0S2Q2)2U0R2W2Z3H0V0A0Y2(1h1|4K2?383E014T0Y4!4f1-070=0Y0x3E0k4v470x0=0S0s0w1v0S0c0V0n1J1D4$3'3_0;000T533.4p0=0i090f0u50594)0-560m4/4;3Q4,0S23090O5i4D5k0=5m4B4:544g0=0}091h0S0S5v3o560F0e3N0k5Q5B5a5D002p4|0f1?2e0O5J5A5o3/0A0=0I5n5C2~0=5W0c0K0w0Y5K3H560T0F5P5R5&5b000Z5Y5+5T1-5(005*5%5,5x000G5@410=0H0A0{0Z6f550=5O6a650-0H27000b0U0h0A0O0D230&0K0h6w6y6A645j0g4+5V316J5w3p6h6j2h5u6q6K1o0=526W6Q055c5e5g5$2_6b0g560C5|5Q5~5U626V6*6r6,0=0L6m5U0Y5s6@4#6+560B6P3o67692@5S6K6t0=6G6z0D2e0k5Y5#055#7g6I4B0P5R7c6$4@055W6}1-5_7z3c5q717C6`005z7b6;5-5V2d0c7l5!6)736_5M6/7u3o6M0a1W1y773H6Y0030723l7X5p611v5:5=7S3l7L6c584I6+6%7N1y7P5Z7n7=2P7@7H5N7W7t857|6i6k7*2P7,5'5)7%6g004-2d7G7B7`6_7|5/7Q828o0=5{7r7t896+6M0w4.6#476S8d8j3_797a388g605F5H834(6Q566p2@7s8A8!856M2J0O0h09188G3H070V0=0v090h8T8Z8#8C4@0%8T858W888!8P2n6M0x6O8+8k0K0A4`6!7K6+7'9c8O8a6&5f5h8q6K566|9m7v008c6U8w000B8X4d919A924*6Z8F9d8r4@0!8e8U5L6{7G7|999b8*6^9n0=76978L5)8N7+857e6v6x7h6C0k6E7p0D9v9y4m9B9;9C7D617x8n9q9M579O0=9Q2B9S7T9U7I8K5U8t815#9v8y8Y9=9B9i619J9v9p9T9ra19g7?749Va7668i9X2n9%9,7j8u7o9'7qae91ah6?ak9~9s6T6l9{5^asawau68at6s6u9,1`0#0O0J9,7W8$0=8&8(a39#8C8.000E3f0H8?194&4L4J2=194N190O4Pa}1{a}0f1)a^034N0@b74Xb90Y0!0$0H00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013hP"b.=0o3[9)egf]xS1lmuq Fd;yTs{:can4vpr6/ 587&_ikéw2t,(}010s0f0T0A0O0m0w0I0z0m0A0w0w08050T0O0E05000q010w0o0n0n0A0F0u000k0a0m0o0/0a0B010H0_0{0}100@0s0O0D0I0|0F0P0s0a0R0B0-0l050I0w0T0u0m0f0-1k0g0O0B0y0l070L0f0n0I0l1J1t0?0X1h0'0)0+0-030O0g030m1X030T0=010!061y1S0*0,051W1Y1!1Y0T1(1y1&0T0F001'030'130w0E0A1q050S1t0(1,0-0h0$0f0B0A0n0f1&22241+1U052c1y2f2h0=020I040F0a0E0a0w0O160B0I0Y200F0F0f0z2D192k0B1|0H0T032Q1`1|2V1'0s2m1-1!0B2e2A1&1g1i292n2$2&2)1&0E2J1|2O2Q2@0^232E2+1-0B0a0F0|0m0=1L2N2{1P2O2!0-30320A34000I0S3724392{3b053d33350b3k2P0@3a2}3c313r3h0C3u3m2l3y3p3A3f350J3E3w3n3H3q3K3h0G3N2`3G1T2~3J3g0I0L3V3x3Y3z3e3#0K3&3P3(3I3*350d3-3X2a3:3B0l093@2|3/3R3g0l0l3~3o420=0l3j1a383O3^2n48000l3t4c3l4e403_4h0l3D4l3v3W4o4g3!493M4t3F4w3Z3;4i3U4B192;0f2Q2)2U0s2W2Z3H0z0a0Y2(1h1|4K2?383E014T0Y4!4f1-0P0=0Y0h3E0I4v470h0=0f0j0O1v0f0N0z031J1D4$3'3_0;000V533.4p0=0g0F0A0E50594)0-560U4/4;3Q4,0f230F0T5i4D5k0=5m4B4:544g0=0}0F1h0f0f5v3o560e0y3N0I5Q5B5a5D002p4|0A1?2e0T5J5A5o3/0a0=085n5C2~0=5W0N0D0O0Y5K3H560V0e5P5R5&5b000Z5Y5+5T1-5(005*5%5,5x000x5@410=0w0a0{0Z6f550=5O6a650-0w27000M0p0o0a0T0t230&0D0o6w6y6A645j054+5V316J5w3p6h6j2h5u6q6K1o0=526W6Q0B5c5e5g5$2_6b05560W5|5Q5~5U626V6*6r6,0=0c6m5U0Y5s6@4#6+560i6P3o67692@5S6K6t0=6G6z0t2e0I5Y5#0B5#7g6I4B0q5R7c6$4@0B5W6}1-5_7z3c5q717C6`005z7b6;5-5V2d0N7l5!6)736_5M6/7u3o6M0R1W1y773H6Y0030723l7X5p611v5:5=7S3l7L6c584I6+6%7N1y7P5Z7n7=2P7@7H5N7W7t857|6i6k7*2P7,5'5)7%6g004-2d7G7B7`6_7|5/7Q828o0=5{7r7t896+6M0O4.6#476S8d8j3_797a388g605F5H834(6Q566p2@7s8A8!856M2J0T0o0F188G3H0P0z0=0v0F0o8T8Z8#8C4@0%8T858W888!8P2n6M0h6O8+8k0D0a4`6!7K6+7'9c8O8a6&5f5h8q6K566|9m7v008c6U8w000i8X4d919A924*6Z8F9d8r4@0!8e8U5L6{7G7|999b8*6^9n0=76978L5)8N7+857e6v6x7h6C0I6E7p0t9v9y4m9B9;9C7D617x8n9q9M579O0=9Q2B9S7T9U7I8K5U8t815#9v8y8Y9=9B9i619J9v9p9T9ra19g7?749Va7668i9X2n9%9,7j8u7o9'7qae91ah6?ak9~9s6T6l9{5^asawau68at6s6u9,1`0#0T0Q9,7W8$0=8&8(a39#8C8.000r3f0w8?194&4L4J2=194N190T4Pa}1{a}0A1)a^0H4N0@b74Xb90Y0!0$0w00
Exercice 10 : existence d'un chemin (parcours en profondeur récursif)

Compléter le code de la fonction récursive existe_chemin qui prend en paramètres un dictionnaire de listes de voisins graphe et deux sommets depart et arrivee, et qui renvoie un booléen indiquant s'il existe un chemin allant de depart et arrivee.

Il y a également un quatrième paramètre etat qui est soit None (par défaut) et un dictionnaire associant à chaque sommet son état. Ce paramètre est utilisé pour les appels récurisif.

On fera une version récursive suivant un parcours en profondeur.

Exemples
>>> existe_chemin_rec(graphe1_dico, 0, 1)
True
>>> existe_chemin_rec(graphe1_dico, 3, 0)
True
>>> existe_chemin_rec(graphe1_dico, 2, 3)
False
>>> existe_chemin_rec(graphe2_dico, 0, 9)
True
>>> existe_chemin_rec(graphe2_dico, 6, 2)
True
>>> existe_chemin_rec(graphe2_dico, 2, 1);
False
>>> existe_chemin_rec(graphe2_dico, 4, 6)
False
Explications de l'algorithme

L'algorithme fonctionne de la façon suivante :

  1. Si l'état est #py None, on marque tous les sommets à non vu.
  2. On regarde si on est arrivé.
  3. Pour chaque voisin de depart non encore vu :
    1. On marque comme vu le voisin et on regarde s'il y a un chemin allant de ce voisin à arrivee.
    2. On marque depart comme traité.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013w}éifs=a3yed9 8S&70gp:n,)6_hro[;"tq2mF/]4xP lk51.vTcN({ub010e0d0A0a060L080K0S0L0a0808090z0A060n0z000g01080W0D0D0a0v0c000i0w0L0W0:0w0p010F0`0|0~110^0e060Q0K0}0v0M0e0w030p0.0O0z0K080A0c0L0d0.1l0m060p0o0O0P0k0d0D0K0O1K1u0@0Y1i0(0*0,0.0u060m0u0L1Y0u0A0?010#0X1z1T0+0-0z1X1Z1#1Z0A1)1z1'0A0v001(0u0(14080n0a1r0z0C1u0)1-0.070%0d0p0a0D0d1'23251,1V0z2d1z2g2i0?020K0J0v0w0n0w0806170p0K0Z210v0v0d0S2E1a2l0p1}0F0A0u2R1{1}2W1(0e2n1.1#0p2f2B1'1h1j2a2o2%2'2*1'0n2K1}2P2R2^0_242F2,1.0p0w0v0}0L0?1M2O2|1Q2P2#0.31330a35000K0C38253a2|3c0z3e34360b3l2Q0^3b2~3d323s3i0H3v3n2m3z3q3B3g360N3F3x3o3I3r3L3i0s3O2{3H1U303K3h0K0k3W3y3Z3A3f3$0h3'3Q3)3J3+360f3.3Y2b3;3C0O0l3^2}3:3S3h0O0O403p430?0O3k1b393P3_2o49000O3u4d3m1a2=0d2R2*2V0e2X2!3I0S0w0Z2)1i1}4p2@393F014y0Z4F4g1.0M0?0Z073F0K3X413`0p070?0d0I061w0d0t0S0u1K1E0t2K0S4H3(3`0=000U4/3/4W0?0m0v0a0n4)4^4M0.4=0q4S4U484P0d240v0A524V2o55574:4h0?0~0v1i0d0d5f3p5i4m2Q4T5k304Z0#5e5v4L5g1.0w0?095s3I0M0S0?0T185r5D583I4=0r0o3O0K5Z5x4_2o4O00064R5D5#533q5A0a5C2^5+5F0.1p0?4$5j5$4N5N005P2&5K3:4=5X5D0g5!695=59000!5/5{5,5H005J5*5T640?0V634`00080w0|0!6q5h0?665;6m3`0828000j0B0W0w0A0y240'0Q0W6H6J6L6g5?0z5&07326U6c6t6v5:396b3I5^5'196l5y3d4{4}505R2`6.0z4=045Y6a5Z6C5l6d5B6x1.4=0x746/000Z5c6&4n6^4=0G6!6)5I7i3:6E0?6R6K0y2f0K5/0A2f7v7p6T6769704N5_5)6B6^0p5a7c7l3`6i096k7G5|795n5p6?4G7f6z6|6}7C0.5&2K0A0W0v6,7Q5,5M0?0R0v0W7V3m685!7#6W0?6Y0v7L710Q0w4$1E7~5G035_7*6'7_7I004|4~515S7X00778h7R5-7a5b0~7d2Q7_7g6A4e6}6~6^5&5(85796e8r5E5t0?8k6@8m8c8183897e8m7g8C0z7N7P8a6^7n6G6I7q6N0K6P7y0y786_7Y7A8x7B7H5.8F8t8I8*8M822C8P8s8i7h6-8m7N8T8Z8(7s7u7w0d8(7Z8.6(3:8A7F8X8L4Z4#4%4'4)0D4+4-8*4=4@8l5,8c8e6=9s0?56919w0?8N8{9A009C7+6V8c7T0Q5q9I9K9i9E726f9v6V5V8v7?9d8x7_7%0!7(8|3i9&5~7/7;9c8b8;9I8J7W9j8o7K9X8H00909L3p939D6V958#6L1{0$0A059b8-8y8m9'7'7)8T7-000E3g087=3w1a4J4q4o2?1a4s1a0A4uaz1|az0a1*au0F4s0^aI4CaK0Z0#0%0800

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013y5T3P/mké94 r"u7ei.0twocg;6]2ld Ff[nx1=_Nq(Sa)p:{8sh,b&v}010x0j0n0L0k0w0R0y0q0w0L0R0R0F0g0n0k0N0g000e010R0h09090L0f03000K0p0w0h0:0p0C01080`0|0~110^0x0k0W0y0}0f0a0x0p0o0C0.0E0g0y0R0n030w0j0.1l0r0k0C0O0E0l0i0j090y0E1K1u0@0Y1i0(0*0,0.0S0k0r0S0w1Y0S0n0?010#0U1z1T0+0-0g1X1Z1#1Z0n1)1z1'0n0f001(0S0(140R0N0L1r0g0v1u0)1-0.0A0%0j0C0L090j1'23251,1V0g2d1z2g2i0?020y070f0p0N0p0R0k170C0y0Z210f0f0j0q2E1a2l0C1}080n0S2R1{1}2W1(0x2n1.1#0C2f2B1'1h1j2a2o2%2'2*1'0N2K1}2P2R2^0_242F2,1.0C0p0f0}0w0?1M2O2|1Q2P2#0.31330L35000y0v38253a2|3c0g3e3436063l2Q0^3b2~3d323s3i0d3v3n2m3z3q3B3g36043F3x3o3I3r3L3i0t3O2{3H1U303K3h0y0i3W3y3Z3A3f3$0Q3'3Q3)3J3+360c3.3Y2b3;3C0E0m3^2}3:3S3h0E0E403p430?0E3k1b393P3_2o49000E3u4d3m1a2=0j2R2*2V0x2X2!3I0q0p0Z2)1i1}4p2@393F014y0Z4F4g1.0a0?0Z0A3F0y3X413`0C0A0?0j0D0k1w0j0G0q0S1K1E0G2K0q4H3(3`0=000J4/3/4W0?0r0f0L0N4)4^4M0.4=0T4S4U484P0j240f0n524V2o55574:4h0?0~0f1i0j0j5f3p5i4m2Q4T5k304Z0#5e5v4L5g1.0p0?0F5s3I0a0q0?0H185r5D583I4=0M0O3O0y5Z5x4_2o4O000k4R5D5#533q5A0L5C2^5+5F0.1p0?4$5j5$4N5N005P2&5K3:4=5X5D0e5!695=59000!5/5{5,5H005J5*5T640?0P634`000R0p0|0!6q5h0?665;6m3`0R28000V0I0h0p0n0s240'0W0h6H6J6L6g5?0g5&0A326U6c6t6v5:396b3I5^5'196l5y3d4{4}505R2`6.0g4=0X5Y6a5Z6C5l6d5B6x1.4=0B746/000Z5c6&4n6^4=0u6!6)5I7i3:6E0?6R6K0s2f0y5/0n2f7v7p6T6769704N5_5)6B6^0C5a7c7l3`6i0F6k7G5|795n5p6?4G7f6z6|6}7C0.5&2K0n0h0f6,7Q5,5M0?050f0h7V3m685!7#6W0?6Y0f7L710W0p4$1E7~5G0o5_7*6'7_7I004|4~515S7X00778h7R5-7a5b0~7d2Q7_7g6A4e6}6~6^5&5(85796e8r5E5t0?8k6@8m8c8183897e8m7g8C0g7N7P8a6^7n6G6I7q6N0y6P7y0s786_7Y7A8x7B7H5.8F8t8I8*8M822C8P8s8i7h6-8m7N8T8Z8(7s7u7w0j8(7Z8.6(3:8A7F8X8L4Z4#4%4'4)094+4-8*4=4@8l5,8c8e6=9s0?56919w0?8N8{9A009C7+6V8c7T0W5q9I9K9i9E726f9v6V5V8v7?9d8x7_7%0!7(8|3i9&5~7/7;9c8b8;9I8J7W9j8o7K9X8H00909L3p939D6V958#6L1{0$0n0b9b8-8y8m9'7'7)8T7-000z3g0R7=3w1a4J4q4o2?1a4s1a0n4uaz1|az0L1*au084s0^aI4CaK0Z0#0%0R00
Pour préparer les exercices suivants

Nous allons maintenant chercher à construire un chemin allant de depart à arrivee s'il existe.

Afin de tester les résultats, nous allons écrire une fonction qui permet de tester si un chemin permet d'aller de depart à arrivee dans un graphe donné.

Exercice 11 : tester si un chemin est valide

Écrire le code de la fonction chemin_valide qui prend un dictionnaire graphe correspondant à un graphe, une liste de sommets chemin et deux sommets depart et arrivee et qui renvoie un booléen indiquant si le chemin permet d'aller de depart à arrivee dans graphe.

Exemples
>>> chemin_valide(graphe1_dico, [0, 1, 2], 0, 2)
True
>>> chemin_valide(graphe1_dico, [0, 1, 2], 0, 3)
False
>>> chemin_valide(graphe1_dico, [0, 1, 3], 0, 3)
False
>>> chemin_valide(graphe1_dico, [0, 1, 2], 1, 2)
False
>>> chemin_valide(graphe2_dico, [6, 5, 0, 1, 3, 4, 7], 6, 7)
True

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.1280134/.7w(cam[Pivf3skT,2+d-1r)e nlS=ogp"0b!]t:Fyu_h56010o0t0I0a0e0x0i0u090x0a0i0i0z0D0I0e0C0D000v010i0M0b0b0a0r0L000y0A0x0M0)0A0w01040:0=0@0_0.0o0e0f0u0?0r0j0o0A070w0'0q0D0u0i0I0L0x0t0'1e0B0e0w0J0q05060t0b0u0q1D1n0-0R1b0Z0#0%0'0O0e0B0O0x1R0O0I0,010U0F1s1M0$0&0D1Q1S1U1S0I1!1s1Y0I0r001Z0O0Z0|0i0C0a1k0D0m1n0!1&0'0g0W0t0w0a0b0t1Y1{1}1%1O0D261s292b0,020u0d0r0A0C0A0i0e100w0u0S1_0r0r0t092x132e0w1?040I0O2K1;1?2P1Z0o2g1'1U0w282u1Y1a1c232h2W2Y2#1Y0C2D1?2I2K2.0/1|2y2%1'0w0A0r0?0x0,0q2H2=1J2I2U0'2_2{0a2}000m311}332=350D372|0,0h3d2J0.342@362`3k00033n3f2f3r3i3t390,0P3x3p3g3A3j3D000Q3G2;3z1N2^3C3a063x132+0t2K2#2O0o2Q2T3A090A0S2!1b1?3Y2-323W3)0S3:3Q240D0j0,0S0g3x0u3P2?3R360g0,090O1D1x0N0f390e0S3W3q450D0+00084i3I4k0w0,0B0r0a0C4a4p3_2h4m0l41433h4s00494b12143;4j3`4C4E4O2h4H0S1|0r0I4z444P0,4D4M3e424S2^0,0@0r1b0t0t4Z3h4m0s0J3G0u4`4(4q3`3|000e404&2J4|4A2^0F0,2k4;3A4m4o543^4!4T484a0b1x5c4k4?4R4}2h0A0,0z0z5r571u0e0,0E5y5i1'1i0,2`5E4G5k4K5o4#000c5O2h5m5C5S1'4m0H5K3A5u000G5x5g565F363}0t4W4Y5(4F5#075I0r5!4r5M5m4L2:4)0'4m5R5g5;4k5$0p5W5A2~694l0,5Z5:600D5$5&5_3`4H4,4.4:646h4m4^5g0v4{6x5)3h502D0I0M0r5}326z3A0j090,0K390i6q2.6w4{654~0,0g5J6g5s4*516l5t5?516G4'6U4T59004v0w0B6Q4N6!610,5f5~6@3i6-5b6r6|5e6c4H4J5|6c5q715z6i0,687a5*0D5U00307f4=0,4@4_6y4`6+1'50526%6#765n7l5d0,636{7b4H0e6c5$0n6c7i7k7E7g5Y7w0'5H002_5/2.6I666'7z7X7s5+004u4w4y7A5p7C745{7#6?7b627.6$7+5P0H0H6u6R7q7q7%3{0,6C6E6)55826K6M6O6=3e6S7r6h6B0T867R3{6L000k0r0M8d3o133?3Z3X2,133#130I3%8B1=8B0a1#8w043#0.8K3-8M0S0U0W0i00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013PpT]hSyutk":.2r(/7Fm=-f4g31+v!aisc) 0 5bln_,o[de6w010N0O0b0x0y0H0z0C0A0H0x0z0z0n0d0b0y040d000E010z0a0m0m0x0h0900080L0H0a0)0L0I010j0:0=0@0_0.0N0y0v0C0?0h0c0N0L0Q0I0'0t0d0C0z0b090H0O0'1e0r0y0I0e0t0f0k0O0m0C0t1D1n0-0R1b0Z0#0%0'070y0r070H1R070b0,010U0G1s1M0$0&0d1Q1S1U1S0b1!1s1Y0b0h001Z070Z0|0z040x1k0d0g1n0!1&0'0p0W0O0I0x0m0O1Y1{1}1%1O0d261s292b0,020C030h0L040L0z0y100I0C0S1_0h0h0O0A2x132e0I1?0j0b072K1;1?2P1Z0N2g1'1U0I282u1Y1a1c232h2W2Y2#1Y042D1?2I2K2.0/1|2y2%1'0I0L0h0?0H0,0t2H2=1J2I2U0'2_2{0x2}000g311}332=350d372|0,0s3d2J0.342@362`3k000q3n3f2f3r3i3t390,0F3x3p3g3A3j3D000P3G2;3z1N2^3C3a0k3x132+0O2K2#2O0N2Q2T3A0A0L0S2!1b1?3Y2-323W3)0S3:3Q240d0c0,0S0p3x0C3P2?3R360p0,0A071D1x0J0v390y0S3W3q450d0+000i4i3I4k0I0,0r0h0x044a4p3_2h4m0K41433h4s00494b12143;4j3`4C4E4O2h4H0S1|0h0b4z444P0,4D4M3e424S2^0,0@0h1b0O0O4Z3h4m0B0e3G0C4`4(4q3`3|000y404&2J4|4A2^0G0,2k4;3A4m4o543^4!4T484a0m1x5c4k4?4R4}2h0L0,0n0n5r571u0y0,0D5y5i1'1i0,2`5E4G5k4K5o4#000M5O2h5m5C5S1'4m065K3A5u000w5x5g565F363}0O4W4Y5(4F5#0Q5I0h5!4r5M5m4L2:4)0'4m5R5g5;4k5$0o5W5A2~694l0,5Z5:600d5$5&5_3`4H4,4.4:646h4m4^5g0E4{6x5)3h502D0b0a0h5}326z3A0c0A0,0l390z6q2.6w4{654~0,0p5J6g5s4*516l5t5?516G4'6U4T59004v0I0r6Q4N6!610,5f5~6@3i6-5b6r6|5e6c4H4J5|6c5q715z6i0,687a5*0d5U00307f4=0,4@4_6y4`6+1'50526%6#765n7l5d0,636{7b4H0y6c5$0u6c7i7k7E7g5Y7w0'5H002_5/2.6I666'7z7X7s5+004u4w4y7A5p7C745{7#6?7b627.6$7+5P06066u6R7q7q7%3{0,6C6E6)55826K6M6O6=3e6S7r6h6B0T867R3{6L00050h0a8d3o133?3Z3X2,133#130b3%8B1=8B0x1#8w0j3#0.8K3-8M0S0U0W0z00
Vous pouvez utiliser cette fonction dans les exercices suivants
Reconstruire le chemin

Nous allons maintenant chercher à construire un chemin allant de depart à arrivee s'il existe. Lors du parcours en largeur, nous allons mémoriser le sommet par lequel nous sommes arrivés à chaque sommet visité. Nous devons donc faire une fonction qui permettra de reconstruire le chemin à partir des prédécesseurs.

Exercice 12 : reconstruire le chemin

Compléter le code de la fonction reconstruit_chemin qui prend en paramètre un dictionnaire precedent associant des sommets à d'autres sommets et deux sommets depart et arrivee, et qui renvoie un chemin allant de depart à arrivee.

On suppose que precedent contient suffisamment d'information pour trouver un chemin allant de depart à arrivee.

Exemples
>>> reconstruit_chemin({0: 1, 1: 2, 2: 3}, 3, 0)
[3, 2, 1, 0]
>>> reconstruit_chemin({1: 2, 2: 4, 3: 0, 4: 0}, 0, 1)
[0, 4, 2, 1]
Explications de l'algorithme

On commence par construire le chemin allant de arrivee à depart.

On dépile alors la liste obtenue (avec liste.pop()) et on construit le chemin final en même temps, comme lorsqu'on retourne une pile en la dépilant sur une autre.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013c60m_.4/319tfsSy&dlo,(n!7[=;u)ar5P]eipgv w:"k 8b2h010k0C0e0x0D0l0g0H030l0x0g0g0t0K0e0D0E0K000M010g0v06060x0y0i000h0m0l0v0)0m0p010a0:0=0@0_0.0k0D0G0H0?0y0L0k0m0I0p0'0c0K0H0g0e0i0l0C0'1e0F0D0p0J0c080r0C060H0c1D1n0-0R1b0Z0#0%0'0Q0D0F0Q0l1R0Q0e0,010U0O1s1M0$0&0K1Q1S1U1S0e1!1s1Y0e0y001Z0Q0Z0|0g0E0x1k0K0P1n0!1&0'0f0W0C0p0x060C1Y1{1}1%1O0K261s292b0,020H0A0y0m0E0m0g0D100p0H0S1_0y0y0C032x132e0p1?0a0e0Q2K1;1?2P1Z0k2g1'1U0p282u1Y1a1c232h2W2Y2#1Y0E2D1?2I2K2.0/1|2y2%1'0p0m0y0?0l0,1F2H2=1J2I2U0'2_2{0x2}000H0P311}332=350K372|2~0b3e2J0.342@362`3l3b093o3g2f3s3j3u392~0z3y3q3h3B3k3E3b043H2;3A1N2^3D3a0H0r3P3r3S3t383V0N3Y3J3!3C3$2~0d3'3R243*3v0c053y132+0C2K2#2O0k2Q2T3B030m0S2!1b1?3`2-323^440S4b3/2h0L0,0S0f3y0H3Q2?3)0p0f0,2D440p1p0y0v2w07030Q1D1x3^3Z3:0+000o4H3(3:0p0,3`030C0S0p0e4N4h1'4K0n4n4p3i4Q000S1|0y4X144c4I2h4#4%4:2^0,0@0y1b0C0C4Y4q4J0,0w0J3H0H574o4@360,4D4F0p072D0e0m0v0y4?4O2h0m0,0t5m4Z0'4K0s504'4_2C4|4~4.3f4&3B4K0B56585F4r4_2F0v0C0l5s515o5q5S5y004`5B5J575L3:4j000I1Q1s5W3K5N0e5P5R5D2J595n1'5p000q5r5=3b5%2h4(4*0@4-2:5a0K4K555~0M586e5@5t3j5.5:5,3)5`5}2.6g5T4^004S4U28664/5^5u0,5w5~616s0x5O5Q5x5G0,5I6c6f5K684(5d061x5g0T5j5l6D685`086J5M5Y0E0E280k6%524L6,626j6I6Z6z69535#6q5X6S4G5~6{3B6n6l6-0s6M2.6d6P6@5'5)2774620O0,2k6/4!0,4M6?6h6R4E6T5f5h6X7k6A000w7f5_0,0j0F0e0u7A1u0D0,3@7o6r7x6b786O5$6Q5c7r6~676@6#7w6i6'6)0p6+7M3i4K7n7X7p7U5e6V5i5k7!7Z7(5-6t2s7!7*0w7z6N7a6h5'5h5k12706E5b006}8778134e3{3_2,133}130e408m1=8m0x1#8h0a3}0.8v488x0S0U0W0g00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013m,uie)0k25bnp6h 3:"a[lgP7w o8=49(rfv&t]1s.c_!ySd;/010O070E0m060o0H0i0J0o0m0H0H0w0l0E060f0l000t010H0503030m0A0M000N0u0o050)0u0e010Q0:0=0@0_0.0O060C0i0?0A0a0O0u0s0e0'0G0l0i0H0E0M0o070'1e0p060e0k0G0I0r07030i0G1D1n0-0R1b0Z0#0%0'0h060p0h0o1R0h0E0,010U0d1s1M0$0&0l1Q1S1U1S0E1!1s1Y0E0A001Z0h0Z0|0H0f0m1k0l0b1n0!1&0'0B0W070e0m03071Y1{1}1%1O0l261s292b0,020i0q0A0u0f0u0H06100e0i0S1_0A0A070J2x132e0e1?0Q0E0h2K1;1?2P1Z0O2g1'1U0e282u1Y1a1c232h2W2Y2#1Y0f2D1?2I2K2.0/1|2y2%1'0e0u0A0?0o0,1F2H2=1J2I2U0'2_2{0m2}000i0b311}332=350l372|2~0j3e2J0.342@362`3l3b0x3o3g2f3s3j3u392~0c3y3q3h3B3k3E3b0g3H2;3A1N2^3D3a0i0r3P3r3S3t383V0v3Y3J3!3C3$2~0y3'3R243*3v0G093y132+072K2#2O0O2Q2T3B0J0u0S2!1b1?3`2-323^440S4b3/2h0a0,0S0B3y0i3Q2?3)0e0B0,2D440e1p0A052w0K0J0h1D1x3^3Z3:0+000z4H3(3:0e0,3`0J070S0e0E4N4h1'4K044n4p3i4Q000S1|0A4X144c4I2h4#4%4:2^0,0@0A1b07074Y4q4J0,080k3H0i574o4@360,4D4F0e0K2D0E0u050A4?4O2h0u0,0w5m4Z0'4K0n504'4_2C4|4~4.3f4&3B4K0F56585F4r4_2F05070o5s515o5q5S5y004`5B5J575L3:4j000s1Q1s5W3K5N0E5P5R5D2J595n1'5p000L5r5=3b5%2h4(4*0@4-2:5a0l4K555~0t586e5@5t3j5.5:5,3)5`5}2.6g5T4^004S4U28664/5^5u0,5w5~616s0m5O5Q5x5G0,5I6c6f5K684(5d031x5g0T5j5l6D685`0I6J5M5Y0f0f280O6%524L6,626j6I6Z6z69535#6q5X6S4G5~6{3B6n6l6-0n6M2.6d6P6@5'5)2774620d0,2k6/4!0,4M6?6h6R4E6T5f5h6X7k6A00087f5_0,0D0p0E0P7A1u060,3@7o6r7x6b786O5$6Q5c7r6~676@6#7w6i6'6)0e6+7M3i4K7n7X7p7U5e6V5i5k7!7Z7(5-6t2s7!7*087z6N7a6h5'5h5k12706E5b006}8778134e3{3_2,133}130E408m1=8m0m1#8h0Q3}0.8v488x0S0U0W0H00
Vous pouvez utiliser cette fonction dans les exercices suivants
Exercice 13 : recherche d'un chemin (parcours en largeur itératif)

Compléter le code de la fonction trouve_chemin qui prend en paramètres un dictionnaire de listes de voisins graphe et deux sommets depart et arrivee, et qui renvoie la liste des sommets formant un chemin allant de depart à arrivee. S'il n'y a pas de chemin, la fonction renvoie une liste vide.

On fera un parcours en largeur utilisant une file d'attente.

⚠ Selon les graphes, la solution n'est pas forcément unique. La solution que vous trouverez ne sera pas forcément la même que dans les exemples. Par contre, avec un parcours en largeur, le chemin trouvé est toujours de longueur minimale.

Exemples
>>> trouve_chemin(graphe2_dico, 0, 5)
[0, 1, 3, 4, 7, 5]
>>> trouve_chemin(graphe2_dico, 6, 9)
[6, 5, 0, 2, 8, 9]
>>> trouve_chemin(graphe1_dico, 0, 2)
[0, 2]
>>> trouve_chemin(graphe1_dico, 0, 3)
[]

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013]4.0cah}d)(y1tNik,v3[=:2b"swerS /u _86pl5{o9gPmf7n010b0v0g080i0G0t0B070G080t0t0o0s0g0i0F0s000y010t0A0N0N080w0e000x0J0G0A0)0J0Q010z0:0=0@0_0.0b0i0l0B0?0w0j0b0J0u0Q0'0f0s0B0t0g0e0G0v0'1e0L0i0Q0p0f050P0v0N0B0f1D1n0-0R1b0Z0#0%0'090i0L090G1R090g0,010U0r1s1M0$0&0s1Q1S1U1S0g1!1s1Y0g0w001Z090Z0|0t0F081k0s0q1n0!1&0'0O0W0v0Q080N0v1Y1{1}1%1O0s261s292b0,020B0M0w0J0F0J0t0i100Q0B0S1_0w0w0v072x132e0Q1?0z0g092K1;1?2P1Z0b2g1'1U0Q282u1Y1a1c232h2W2Y2#1Y0F2D1?2I2K2.0/1|2y2%1'0Q0J0w0?0G0,1F2H2=1J2I2U0'2_2{082}000B0q311}332=350s372|2~0m3e2J0.342@362`3l3b043o3g2f3s3j3u392~0H3y3q3h3B3k3E3b0E3H2;3A1N2^3D3a0B0P3P3r3S3t383V0D3Y3J3!3C3$2~0K3'3R243*3v0f063.2?3)3L3a0f0f3^3i3{0,0f3d14323I3/2h42000f3n463f483_3:4b0f3x4f2J132+0v2K2#2O0b2Q2T3B070J0S2!1b1?4q2-323y014z0S4G491'0j0,0S0O3y0B3Q4i4a0O0,1;0J0A0l0v0C07091D1x4I3Z3:0+000d4,3(4j0,0L0w080F4)4=4N0'4/0k4T4V414Q0v1|0w0g4~4W1'52544-4a0,0@0w1b0v0v5c3i4/0c0p3H0B5v4U5h2^0,2j4&081-280g5o4n3b553B0J0,0o5g4?5i005B0C0l0i0S5p3B4/0d0c5u5w5K3`0,4q070v0S0Q5b5I5x5Q1'5M005O5:5'4.0,0I5Y5(000t0J0=0T605|005t5`5y0'0j070,0h115H2.5;500s4P5S2`5P6m0Q0,63655/6k5{2h1i0,4+6b5=364^4`4|6j4H6c0s4/0a5%5v6z5z00285B672h5!6X6T0S596x6L6F6N0,536E6s5A270C5D5G5.6K3f6S510,5$5I0y5w6l5d6d0,0u1Q1s6r720s6B002_6&3f71566U1p5U5W6@4o6M6Z5I6_3j6.1s6:5E6?6!6`005s6Q707g3K6u642b7e2J7E3)5@5_6y6M6t004R277y6)4:7V7R5T6;5F7m4M795r7C707r6o0i4S6,797R6v7I783i7N7O327L4@005k5m7%7r4/6a2.6~7D887+0,2D0g0A0w127/7h2D4z0Q1p0w0A2w4'4)0N6D2:7o0,4;7q7Q5)8j5,5F7V5f8h7F7S580@7J7&5q6*7@8H804%828v7A7)5&6M6o0v0X8T6(848W898Y5A6q8G610l0J0i2v8g7P6(7b8t7{7r7R4_4{4}8y8%0,0n7Y7G6w8E0,038547889d8X6(7,7.8?6-005*8C5.980094919k8.8:8_6^8U038P7M0u6C0t9A3:6e6g6i9p9b4g9e9N9f9k6V7U9s7'8w95009u8;9p6+9j7:7t5C7w5G9p6|869O9O8{8A2E9n8L83939W9Y9w7n92009z8,3:7N9F5R7=666}7*8)008c8e8=8`8U0na086134K4r4p2,134t130g4var1=ar081#am0z4t0.aA4DaC0S0U0W0t00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013,6/vhl.sw([go nkP]y)au8tcpm10_e25:{Nd"}rSfi =97b43010D0x0q0n0J080a0g0r080n0a0a0L0E0q0J0s0E000K010a0o0t0t0n0G0l000H0f080o0)0f0h01050:0=0@0_0.0D0J060g0?0G0i0D0f0b0h0'0u0E0g0a0q0l080x0'1e0e0J0h0A0u090N0x0t0g0u1D1n0-0R1b0Z0#0%0'070J0e07081R070q0,010U0O1s1M0$0&0E1Q1S1U1S0q1!1s1Y0q0G001Z070Z0|0a0s0n1k0E0y1n0!1&0'0I0W0x0h0n0t0x1Y1{1}1%1O0E261s292b0,020g0j0G0f0s0f0a0J100h0g0S1_0G0G0x0r2x132e0h1?050q072K1;1?2P1Z0D2g1'1U0h282u1Y1a1c232h2W2Y2#1Y0s2D1?2I2K2.0/1|2y2%1'0h0f0G0?080,1F2H2=1J2I2U0'2_2{0n2}000g0y311}332=350E372|2~0Q3e2J0.342@362`3l3b0P3o3g2f3s3j3u392~0z3y3q3h3B3k3E3b043H2;3A1N2^3D3a0g0N3P3r3S3t383V0p3Y3J3!3C3$2~0M3'3R243*3v0u0v3.2?3)3L3a0u0u3^3i3{0,0u3d14323I3/2h42000u3n463f483_3:4b0u3x4f2J132+0x2K2#2O0D2Q2T3B0r0f0S2!1b1?4q2-323y014z0S4G491'0i0,0S0I3y0g3Q4i4a0I0,1;0f0o060x0w0r071D1x4I3Z3:0+000c4,3(4j0,0e0G0n0s4)4=4N0'4/034T4V414Q0x1|0G0q4~4W1'52544-4a0,0@0G1b0x0x5c3i4/0m0A3H0g5v4U5h2^0,2j4&0n1-280q5o4n3b553B0f0,0L5g4?5i005B0w060J0S5p3B4/0c0m5u5w5K3`0,4q0r0x0S0h5b5I5x5Q1'5M005O5:5'4.0,0B5Y5(000a0f0=0T605|005t5`5y0'0i0r0,0C115H2.5;500E4P5S2`5P6m0h0,63655/6k5{2h1i0,4+6b5=364^4`4|6j4H6c0E4/0F5%5v6z5z00285B672h5!6X6T0S596x6L6F6N0,536E6s5A270w5D5G5.6K3f6S510,5$5I0K5w6l5d6d0,0b1Q1s6r720E6B002_6&3f71566U1p5U5W6@4o6M6Z5I6_3j6.1s6:5E6?6!6`005s6Q707g3K6u642b7e2J7E3)5@5_6y6M6t004R277y6)4:7V7R5T6;5F7m4M795r7C707r6o0J4S6,797R6v7I783i7N7O327L4@005k5m7%7r4/6a2.6~7D887+0,2D0q0o0G127/7h2D4z0h1p0G0o2w4'4)0t6D2:7o0,4;7q7Q5)8j5,5F7V5f8h7F7S580@7J7&5q6*7@8H804%828v7A7)5&6M6o0x0X8T6(848W898Y5A6q8G61060f0J2v8g7P6(7b8t7{7r7R4_4{4}8y8%0,0d7Y7G6w8E0,0k8547889d8X6(7,7.8?6-005*8C5.980094919k8.8:8_6^8U0k8P7M0b6C0a9A3:6e6g6i9p9b4g9e9N9f9k6V7U9s7'8w95009u8;9p6+9j7:7t5C7w5G9p6|869O9O8{8A2E9n8L83939W9Y9w7n92009z8,3:7N9F5R7=666}7*8)008c8e8=8`8U0da086134K4r4p2,134t130q4var1=ar0n1#am054t0.aA4DaC0S0U0W0a00
Exercice 14 : recherche d'un chemin (parcours en profondeur récursif)

Compléter le code de la fonction récursive trouve_chemin_rec qui prend en paramètres un dictionnaire de listes de voisins graphe et deux sommets depart et arrivee, et qui renvoie la liste des sommets formant un chemin allant de depart à arrivee. S'il n'y a pas de chemin, la fonction renvoie une liste vide.

Il y a paramètre supplémentaire qui s'appelle chemin et qui vaut None par défaut. Ce paramètre est utilisé pour les appels récursifs. Il sert à mémoriser le chemin parcouru jusqu'ici.

On fera un parcours en profondeur en utilisant la récursivité.

⚠ Selon les graphes, la solution n'est pas forcément unique. La solution que vous trouverez ne sera pas forcément la même que dans les exemples. La solution n'est pas forcément de longueur minimale.

Exemples
>>> trouve_chemin_rec(graphe2_dico, 0, 5)
[0, 1, 3, 4, 7, 5]
>>> trouve_chemin_rec(graphe2_dico, 6, 9)
[6, 5, 0, 1, 3, 2, 8, 9]
>>> trouve_chemin_rec(graphe1_dico, 0, 2)
[0, 1, 2]
>>> trouve_chemin_rec(graphe1_dico, 0, 3)
[]
Explications de l'algorithme
  1. Si chemin est None, on l'initialise avec la liste vide.
  2. On rajoute depart à chemin.
  3. On regarde si on est arrivé.
  4. Sinon on parcourt tous les voisins de depart.
    1. Pour chaque voisin de depart, on regarde s'il permet d'aller à arrivee.
    2. Si c'est le cas, on a notre réponse.
  5. Si on n'a rien trouvé, on retire depart de la liste et on renvoie une liste vide.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013S/k5=ir[)b(gen&ou:0y.wsh_6pcfv1]92;34dNt7" 8P ,mal010E0f0G0P080Q0p0M0u0Q0P0p0p070I0G080t0I000J010p0j0O0O0P090m00030i0Q0j0)0i0g01040:0=0@0_0.0E080w0M0?09050E0i0o0g0'0x0I0M0p0G0m0Q0f0'1e0e080g0k0x0n0H0f0O0M0x1D1n0-0R1b0Z0#0%0'0q080e0q0Q1R0q0G0,010U0c1s1M0$0&0I1Q1S1U1S0G1!1s1Y0G09001Z0q0Z0|0p0t0P1k0I0A1n0!1&0'0v0W0f0g0P0O0f1Y1{1}1%1O0I261s292b0,020M0L090i0t0i0p08100g0M0S1_09090f0u2x132e0g1?040G0q2K1;1?2P1Z0E2g1'1U0g282u1Y1a1c232h2W2Y2#1Y0t2D1?2I2K2.0/1|2y2%1'0g0i090?0Q0,1F2H2=1J2I2U0'2_2{0P2}000M0A311}332=350I372|2~0C3e2J0.342@362`3l3b0D3o3g2f3s3j3u392~063y3q3h3B3k3E3b0s3H2;3A1N2^3D3a0M0H3P3r3S3t383V0K3Y3J3!3C3$2~0z3'3R243*3v0x0l3.2?3)3L3a0x0x3^3i3{0,0x3d14323I3/2h42000x3n463f132+0f2K2#2O0E2Q2T3B0u0i0S2!1b1?4i2-323y014r0S4y491'050,0S0v3y0M3Q3_3:0g0v0,1;0i0j0w0f0r0u0q1D1x0r2D0u4A3Z3:0+000d4(3(4P0,0e090P0t4!4.4F0'4+0N4L4N414I0f1|090G4`4O2h4}504)4a0,0@091b0f0f583i5b4f2J4M5d2^0,4Z4#125o4E591'0i0,075l3B050u0,0F115k5x513B4+0b0k3H0M5T5q4/2h4H00084K5x5V4{3j5t4!0O1x5c5W5A0o0,080p5,5&5G5I5K5E3)4+5R5x0J5U625%5z365(5v5?650I5B005D5$5N5|0,0a0y5S5U6g4:005u5*5w2:5r0'6c0n5{6o4@0t280E6y5a0,4-5M6u5'000S55576I5-4|0,0b6l5T6n5X5:5#2.64526L540@6O6!6W5A5C6e6)6J0g5f2C5i5L6t6Q0I5}6U636*0'5Y2D0G0j096s326#3K676r6|6~0I5Y0v2`696$0w0i5;5+6f6J1i5:763f783`4;4?4^6@4z6J4+0a6E5s6%6N7E6R000y5~2.61636V6J5Y5!7i79007k7m7s5p7d7q002_6(777#5/5Z7Z3b7d6:6p5)7n6^5&6{607P7P7.7a1x456.6_6c6-7(6/4S2r4V4X6q4$4&7I6`6G8e7/4=4@4_6P7@0,4~7o6_7/7X2v7,7d5n815&7/5g6?8e8x858r7}8v7B6S6|7`7u3:7S6Z8F8z0c0,2k8D8g8m6a7/8b0g807A6_5P7U3)6c0h0e0G0B8)3:5*0,3@8Y5m0,7M478M8M7d710T747,8N5e7:5v8%3f7O7Q8G977b8^3B6w8h0,2t0t8W4,6T7_6m7R0,72938:6F006j3P044C4j4h2,134l130G4n9I1=9I0P1#9D044l0.9R4v9T0S0U0W0p00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013ac2mo1Sd&0ny9.3P[(r=;8]N:ht,swk)7 _ pgef"u/v54bli6010a0F0t030P0O0v0C040O030v0v0m0H0t0P0D0H000A010v0I0606030l0e0009070O0I0)070d010J0:0=0@0_0.0a0P0K0C0?0l0x0a070w0d0'080H0C0v0t0e0O0F0'1e0E0P0d0r080g0z0F060C081D1n0-0R1b0Z0#0%0'0s0P0E0s0O1R0s0t0,010U0N1s1M0$0&0H1Q1S1U1S0t1!1s1Y0t0l001Z0s0Z0|0v0D031k0H051n0!1&0'0G0W0F0d03060F1Y1{1}1%1O0H261s292b0,020C0i0l070D070v0P100d0C0S1_0l0l0F042x132e0d1?0J0t0s2K1;1?2P1Z0a2g1'1U0d282u1Y1a1c232h2W2Y2#1Y0D2D1?2I2K2.0/1|2y2%1'0d070l0?0O0,1F2H2=1J2I2U0'2_2{032}000C05311}332=350H372|2~0h3e2J0.342@362`3l3b0M3o3g2f3s3j3u392~0L3y3q3h3B3k3E3b0Q3H2;3A1N2^3D3a0C0z3P3r3S3t383V0o3Y3J3!3C3$2~0f3'3R243*3v080c3.2?3)3L3a08083^3i3{0,083d14323I3/2h4200083n463f132+0F2K2#2O0a2Q2T3B04070S2!1b1?4i2-323y014r0S4y491'0x0,0S0G3y0C3Q3_3:0d0G0,1;070I0K0F0B040s1D1x0B2D044A3Z3:0+000k4(3(4P0,0E0l030D4!4.4F0'4+0u4L4N414I0F1|0l0t4`4O2h4}504)4a0,0@0l1b0F0F583i5b4f2J4M5d2^0,4Z4#125o4E591'070,0m5l3B0x040,0q115k5x513B4+0y0r3H0C5T5q4/2h4H000P4K5x5V4{3j5t4!061x5c5W5A0w0,0P0v5,5&5G5I5K5E3)4+5R5x0A5U625%5z365(5v5?650H5B005D5$5N5|0,0j0p5S5U6g4:005u5*5w2:5r0'6c0g5{6o4@0D280a6y5a0,4-5M6u5'000S55576I5-4|0,0y6l5T6n5X5:5#2.64526L540@6O6!6W5A5C6e6)6J0d5f2C5i5L6t6Q0H5}6U636*0'5Y2D0t0I0l6s326#3K676r6|6~0H5Y0G2`696$0K075;5+6f6J1i5:763f783`4;4?4^6@4z6J4+0j6E5s6%6N7E6R000p5~2.61636V6J5Y5!7i79007k7m7s5p7d7q002_6(777#5/5Z7Z3b7d6:6p5)7n6^5&6{607P7P7.7a1x456.6_6c6-7(6/4S2r4V4X6q4$4&7I6`6G8e7/4=4@4_6P7@0,4~7o6_7/7X2v7,7d5n815&7/5g6?8e8x858r7}8v7B6S6|7`7u3:7S6Z8F8z0N0,2k8D8g8m6a7/8b0d807A6_5P7U3)6c0b0E0t0n8)3:5*0,3@8Y5m0,7M478M8M7d710T747,8N5e7:5v8%3f7O7Q8G977b8^3B6w8h0,2t0D8W4,6T7_6m7R0,72938:6F006j3P0J4C4j4h2,134l130t4n9I1=9I031#9D0J4l0.9R4v9T0S0U0W0v00
Exercice 15 : recherche d'un chemin optimal (parcours en profondeur récursif)

Compléter le code de la fonction récursive trouve_chemin_opti_rec qui prend en paramètres un dictionnaire de listes de voisins graphe et deux sommets depart et arrivee, et qui renvoie la liste des sommets formant un chemin de longueur minimale allant de depart à arrivee. S'il n'y a pas de chemin, la fonction renvoie une liste vide.

Il y a paramètre supplémentaire qui s'appelle chemin et qui vaut None par défaut. Ce paramètre est utilisé pour les appels récursifs. Il sert à mémoriser le chemin parcouru jusqu'ici.

On fera un parcours en profondeur en utilisant la récursivité.

⚠ Selon les graphes, la solution n'est pas forcément unique. Par contre, il faut qu'elle soit optimale, c'est-à-dire la plus petite possible.

Exemples
>>> trouve_chemin_rec(graphe2_dico, 0, 5)
[0, 1, 3, 4, 7, 5]
>>> trouve_chemin_rec(graphe2_dico, 6, 9)
[6, 5, 0, 1, 3, 2, 8, 9]
>>> trouve_chemin_rec(graphe1_dico, 0, 2)
[0, 1, 2]
>>> trouve_chemin_rec(graphe1_dico, 0, 3)
[]
Explications de l'algorithme

On fait à peu près la même chose que dans l'exercice précédent sauf qu'au lieu de renvoyer le premier chemin trouvé, on les teste tous pour trouver le plus court.

Par contre, on ajoute les sommets à chemin dans la boucle pour pouvoir les retirer avant de faire un return.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013.(k7,]hv[9Ptds/Sw op_lf+2a"8:u&;i 0rye3)mnNg4cb=165010f0E0e0s0z0o0g0A0M0o0s0g0g0O0t0e0z0m0t000k010g0w0H0H0s0C0D000i0l0o0w0*0l0I010h0;0?0^0`0/0f0z0a0A0@0C050f0l0j0I0(0P0t0A0g0e0D0o0E0(1f0K0z0I0v0P03060E0H0A0P1E1o0.0S1c0!0$0&0(090z0K090o1S090e0-010V0N1t1N0%0'0t1R1T1V1T0e1#1t1Z0e0C001!090!0}0g0m0s1l0t0r1o0#1'0(0p0X0E0I0s0H0E1Z1|1~1&1P0t271t2a2c0-020A0d0C0l0m0l0g0z110I0A0T1`0C0C0E0M2y142f0I1@0h0e092L1=1@2Q1!0f2h1(1V0I292v1Z1b1d242i2X2Z2$1Z0m2E1@2J2L2/0:1}2z2&1(0I0l0C0@0o0-1G2I2?1K2J2V0(2`2|0s2~000A0r321~342?360t382}300F3f2K0/352^372{3m3c0L3p3h2g3t3k3v3a300R3z3r3i3C3l3F3c0Q3I2=3B1O2_3E3b0A063Q3s3T3u393W0u3Z3K3#3D3%300c3(3S253+3w0P0B3/2@3*3M3b0P0P3_3j3|0-0P3e15333J3:2i43000P3o473g493`3;4c0P3y4g3q3R4j4b3V443H4o3A4r3U3,4d3P4w142,0E2L2$2P0f2R2U3C0M0l0T2#1c1@4F2.333z014O0T4V4a1(050-0T0p3z0A4q420p0-1=0l0w0a0E0n0M091E1y0n2t0*0n2E0M4X3!3;0,0004543)4k0-0K0C0s0m4`5a4$0(57074*4,3L4'0E1}0C0e5j4y5l0-5n4w4+554b0-0^0C1c0E0E5w3j5m5o5D2_0-4_4{134D5P0(0l0-0O5L3C050M0-0J125K5V5b2i570G0v3I0A5=5C5,4%0-0z4)5B5p3{5R4`0H1y5O5^5X0j5`0g655k0t5%5'5)5#3*575:4w0k5?6n5@6c0I615T6b5x0t5Y005!5}5W0t570b6h5c000T5t5v5+6c57085;5?5~3;4&005{6u425r6J6W3C6x0O6z2/6p6v6r005G5I5*2;6B6j6P6o6(3j6T2E0e0w0C5U6'6R5E005S636~486n715Q73624|750z6!3*6$7g560-0b6O6l786B6*0o120K0w0E6|0n7e7j2i7i6A663k0N0-2l6F5-0-596L6)5d5f5h6.4W6:0-0G7J1(6x0q7X1v0z446=6@5$0-0p2{7A7a0a0l0z2w763g7(7h686U7?2K7^6G5e5g5i7N5M7l7#3k6Y0^6K6/7E6N6k2/6m6?7~2i6T6V7D6q0-7/7;648n6v1j0-2`8b338j7Y7`8s707q6s75876;7o8i7p7E6*748D7T7E6x03876*5g0m290f8I7L8V8p7:7=8#007W8K8L5=79378G1y468E8S5Z7-8:004:4=4@8P0I4}0m50528)7M8c8o00817R8)5A8@9a8q8(843C5N8t6X6+2D6-9e8`887b6t9k6i7V7'8L8/6d5`5|9g6)7G007I9x7k588%9v758?8R6M9z9n6#0-0x0K0e0y9t630-3^9V7_5F0I8!9(4k9I9K996v57989S7O9P8=8)8+9G3j6x0x0o9!9t7r7t7v7x7z9L7K008f778-6?9Ca60I7u7w0C7y1y7f9-7B8_ar2_9/29979O919R3g9C5.9Aag8A8{91ao0Iaq9~9W6ya59/7;8yaC7U9Nab7aaA9|aFah8F9`7|4#8u0-8UaX8{2u0m979}af8.6B6_0U6|a'aH9uaJaa8g144Z4G4E2-144I140e4Kb91?b90s1$b40h4I0/bi4Sbk0T0V0X0g00

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013n;8kpigy,1e/l5Nsfh23_P0d(7."aru] S[=bv+:o)wm946t c&010q0d0O0v080f0i0P0Q0f0v0i0i0C0u0O08070u000z010i0x0K0K0v0w0a000A0H0f0x0*0H03010e0;0?0^0`0/0q080E0P0@0w060q0H0J030(0c0u0P0i0O0a0f0d0(1f0908030G0c0t0s0d0K0P0c1E1o0.0S1c0!0$0&0(0k08090k0f1S0k0O0-010V0D1t1N0%0'0u1R1T1V1T0O1#1t1Z0O0w001!0k0!0}0i070v1l0u0l1o0#1'0(0j0X0d030v0K0d1Z1|1~1&1P0u271t2a2c0-020P0o0w0H070H0i0811030P0T1`0w0w0d0Q2y142f031@0e0O0k2L1=1@2Q1!0q2h1(1V03292v1Z1b1d242i2X2Z2$1Z072E1@2J2L2/0:1}2z2&1(030H0w0@0f0-1G2I2?1K2J2V0(2`2|0v2~000P0l321~342?360u382}300m3f2K0/352^372{3m3c0M3p3h2g3t3k3v3a300g3z3r3i3C3l3F3c0N3I2=3B1O2_3E3b0P0s3Q3s3T3u393W053Z3K3#3D3%300L3(3S253+3w0c0p3/2@3*3M3b0c0c3_3j3|0-0c3e15333J3:2i43000c3o473g493`3;4c0c3y4g3q3R4j4b3V443H4o3A4r3U3,4d3P4w142,0d2L2$2P0q2R2U3C0Q0H0T2#1c1@4F2.333z014O0T4V4a1(060-0T0j3z0P4q420j0-1=0H0x0E0d0n0Q0k1E1y0n2t0*0n2E0Q4X3!3;0,000r543)4k0-090w0v074`5a4$0(570b4*4,3L4'0d1}0w0O5j4y5l0-5n4w4+554b0-0^0w1c0d0d5w3j5m5o5D2_0-4_4{134D5P0(0H0-0C5L3C060Q0-0h125K5V5b2i570I0G3I0P5=5C5,4%0-084)5B5p3{5R4`0K1y5O5^5X0J5`0i655k0u5%5'5)5#3*575:4w0z5?6n5@6c03615T6b5x0u5Y005!5}5W0u570B6h5c000T5t5v5+6c570y5;5?5~3;4&005{6u425r6J6W3C6x0C6z2/6p6v6r005G5I5*2;6B6j6P6o6(3j6T2E0O0x0w5U6'6R5E005S636~486n715Q73624|75086!3*6$7g560-0B6O6l786B6*0f12090x0d6|0n7e7j2i7i6A663k0D0-2l6F5-0-596L6)5d5f5h6.4W6:0-0I7J1(6x0F7X1v08446=6@5$0-0j2{7A7a0E0H082w763g7(7h686U7?2K7^6G5e5g5i7N5M7l7#3k6Y0^6K6/7E6N6k2/6m6?7~2i6T6V7D6q0-7/7;648n6v1j0-2`8b338j7Y7`8s707q6s75876;7o8i7p7E6*748D7T7E6x0t876*5g07290q8I7L8V8p7:7=8#007W8K8L5=79378G1y468E8S5Z7-8:004:4=4@8P034}0750528)7M8c8o00817R8)5A8@9a8q8(843C5N8t6X6+2D6-9e8`887b6t9k6i7V7'8L8/6d5`5|9g6)7G007I9x7k588%9v758?8R6M9z9n6#0-0R090O049t630-3^9V7_5F038!9(4k9I9K996v57989S7O9P8=8)8+9G3j6x0R0f9!9t7r7t7v7x7z9L7K008f778-6?9Ca6037u7w0w7y1y7f9-7B8_ar2_9/29979O919R3g9C5.9Aag8A8{91ao03aq9~9W6ya59/7;8yaC7U9Nab7aaA9|aFah8F9`7|4#8u0-8UaX8{2u07979}af8.6B6_0U6|a'aH9uaJaa8g144Z4G4E2-144I140O4Kb91?b90v1$b40e4I0/bi4Sbk0T0V0X0i00