#Lien pour déposer votre fichier : https://nuage03.apps.education.fr/index.php/s/Jj749DgpAL7Ly36 ######################################## # Structures de données fournies # ######################################## arrets = {1: 'Cité du Marché 1', 5: 'Pont de la Montagne 5', 96: 'Avenue des Fleurs 96', 2: 'Boulevard des Fleurs 2', 19: 'Quai de la Tour 19', 15: 'Parc de la République 15', 3: 'Pont des Écoles 3', 77: 'Hôpital de la Gare 77', 56: 'Stade des Fleurs 56', 4: 'Théâtre de la République 4', 29: 'Cité des Sports 29', 31: 'Hôpital de la Fontaine 31', 73: 'Parc des Fleurs 73', 27: 'École de Verdun 27', 6: 'Marché des Sports 6', 30: 'Parc de la République 30', 59: 'Théâtre du Stade 59', 37: 'Place du Stade 37', 7: 'Impasse de la Gare 7', 45: 'Marché de Verdun 45', 21: 'Passage du Marché 21', 99: 'Hôpital des Arts 99', 8: 'Théâtre de Verdun 8', 46: 'Pont de la Montagne 46', 79: 'Quai du Lac 79', 35: 'Passage du Marché 35', 9: 'Boulevard des Arts 9', 50: 'Stade de la Fontaine 50', 12: 'Jardin des Tilleuls 12', 10: 'Cité des Écoles 10', 75: 'Hôpital des Écoles 75', 26: 'Avenue de la Liberté 26', 92: 'Impasse de la Paix 92', 11: 'Théâtre du Centre 11', 14: 'Avenue du Stade 14', 22: 'Stade de la Rivière 22', 49: 'Jardin de la Tour 49', 47: 'Jardin de la Rivière 47', 28: 'École de la Montagne 28', 13: 'Gare du Château 13', 83: 'Gare du Marché 83', 61: 'Boulevard de la Paix 61', 89: 'Pont de la Montagne 89', 43: 'Place de la Gare 43', 100: 'Rue de Verdun 100', 16: 'Gare de la Rivière 16', 42: 'Hôpital des Alouettes 42', 53: 'Passage de Verdun 53', 17: 'Boulevard de la Tour 17', 74: 'Rue de la Liberté 74', 93: 'Passage de la Gare 93', 18: 'Jardin des Alouettes 18', 84: 'Cité du Marché 84', 60: 'Cité des Arts 60', 20: 'Allée du Stade 20', 76: 'Avenue des Sports 76', 48: 'Stade du Stade 48', 78: 'Théâtre du Centre 78', 69: 'Hôpital des Écoles 69', 34: 'Passage de la Fontaine 34', 72: 'Hôpital des Alouettes 72', 23: 'École de la Tour 23', 24: 'Théâtre de la Liberté 24', 94: 'Allée de Verdun 94', 66: 'Passage du Centre 66', 25: 'Parc de Verdun 25', 41: 'Square de la Rivière 41', 95: 'Allée des Tilleuls 95', 70: 'Place de la Montagne 70', 86: 'Marché des Alouettes 86', 62: 'Pont de Verdun 62', 71: 'Pont de la Rivière 71', 98: 'École du Marché 98', 90: 'Cité du Centre 90', 32: 'Allée de la Rivière 32', 58: 'Hôpital de la Liberté 58', 68: 'Pont du Lac 68', 33: 'Impasse du Château 33', 36: 'Passage des Tilleuls 36', 44: 'Pont de Verdun 44', 87: 'École des Arts 87', 64: 'Pont de la République 64', 38: 'Impasse de la Gare 38', 39: 'Square de la Tour 39', 57: 'Impasse de la Paix 57', 40: 'Hôpital des Tilleuls 40', 88: 'Théâtre de la Tour 88', 85: 'Square du Stade 85', 54: 'Boulevard de la Paix 54', 51: 'Jardin des Alouettes 51', 91: 'Cité des Écoles 91', 97: 'Place de la Tour 97', 52: 'Passage des Arts 52', 63: 'Jardin des Fleurs 63', 67: 'Rue des Tilleuls 67', 55: 'Parc des Écoles 55', 80: 'Théâtre des Arts 80', 65: 'Stade du Lac 65', 81: 'Avenue de Verdun 81', 82: 'Boulevard des Tilleuls 82'} graphe = {1: [{'distance': 5, 'nom': 'Pont de la Montagne 5', 'numero': 5}, {'distance': 4, 'nom': 'Avenue des Fleurs 96', 'numero': 96}], 2: [{'distance': 11, 'nom': 'Quai de la Tour 19', 'numero': 19}, {'distance': 12, 'nom': 'Avenue des Fleurs 96', 'numero': 96}, {'distance': 15, 'nom': 'Parc de la République 15', 'numero': 15}], 3: [{'distance': 1, 'nom': 'Hôpital de la Gare 77', 'numero': 77}, {'distance': 1, 'nom': 'Stade des Fleurs 56', 'numero': 56}], 4: [{'distance': 9, 'nom': 'Cité des Sports 29', 'numero': 29}, {'distance': 10, 'nom': 'Hôpital de la Fontaine 31', 'numero': 31}], 5: [{'distance': 5, 'nom': 'Cité du Marché 1', 'numero': 1}, {'distance': 12, 'nom': 'Parc des Fleurs 73', 'numero': 73}, {'distance': 11, 'nom': 'École de Verdun 27', 'numero': 27}], 6: [{'distance': 13, 'nom': 'Parc de la République 30', 'numero': 30}, {'distance': 13, 'nom': 'Théâtre du Stade 59', 'numero': 59}, {'distance': 3, 'nom': 'Hôpital de la Gare 77', 'numero': 77}, {'distance': 12, 'nom': 'Place du Stade 37', 'numero': 37}], 7: [{'distance': 6, 'nom': 'Marché de Verdun 45', 'numero': 45}, {'distance': 2, 'nom': 'Place du Stade 37', 'numero': 37}, {'distance': 2, 'nom': 'Passage du Marché 21', 'numero': 21}, {'distance': 7, 'nom': 'Cité des Sports 29', 'numero': 29}, {'distance': 2, 'nom': 'Hôpital des Arts 99', 'numero': 99}], 8: [{'distance': 12, 'nom': 'Pont de la Montagne 46', 'numero': 46}, {'distance': 8, 'nom': 'Quai du Lac 79', 'numero': 79}, {'distance': 9, 'nom': 'Passage du Marché 35', 'numero': 35}], 9: [{'distance': 9, 'nom': 'Stade de la Fontaine 50', 'numero': 50}, {'distance': 5, 'nom': 'Jardin des Tilleuls 12', 'numero': 12}], 10: [{'distance': 1, 'nom': 'Hôpital des Écoles 75', 'numero': 75}, {'distance': 11, 'nom': 'Avenue de la Liberté 26', 'numero': 26}, {'distance': 4, 'nom': 'Impasse de la Paix 92', 'numero': 92}], 11: [{'distance': 5, 'nom': 'Jardin des Tilleuls 12', 'numero': 12}, {'distance': 8, 'nom': 'Hôpital de la Fontaine 31', 'numero': 31}, {'distance': 11, 'nom': 'Avenue du Stade 14', 'numero': 14}, {'distance': 14, 'nom': 'Stade de la Fontaine 50', 'numero': 50}], 12: [{'distance': 5, 'nom': 'Boulevard des Arts 9', 'numero': 9}, {'distance': 5, 'nom': 'Théâtre du Centre 11', 'numero': 11}, {'distance': 11, 'nom': 'Stade de la Rivière 22', 'numero': 22}, {'distance': 5, 'nom': 'Jardin de la Tour 49', 'numero': 49}, {'distance': 12, 'nom': 'Jardin de la Rivière 47', 'numero': 47}, {'distance': 15, 'nom': 'École de la Montagne 28', 'numero': 28}], 13: [{'distance': 3, 'nom': 'Quai du Lac 79', 'numero': 79}, {'distance': 9, 'nom': 'Gare du Marché 83', 'numero': 83}], 14: [{'distance': 11, 'nom': 'Théâtre du Centre 11', 'numero': 11}, {'distance': 5, 'nom': 'Stade de la Rivière 22', 'numero': 22}, {'distance': 15, 'nom': 'Boulevard de la Paix 61', 'numero': 61}, {'distance': 11, 'nom': 'Stade de la Fontaine 50', 'numero': 50}], 15: [{'distance': 15, 'nom': 'Boulevard des Fleurs 2', 'numero': 2}, {'distance': 13, 'nom': 'Pont de la Montagne 89', 'numero': 89}, {'distance': 1, 'nom': 'Place de la Gare 43', 'numero': 43}, {'distance': 4, 'nom': 'Rue de Verdun 100', 'numero': 100}], 16: [{'distance': 5, 'nom': 'Hôpital des Alouettes 42', 'numero': 42}, {'distance': 2, 'nom': 'Passage de Verdun 53', 'numero': 53}], 17: [{'distance': 4, 'nom': 'Rue de la Liberté 74', 'numero': 74}, {'distance': 11, 'nom': 'Passage de la Gare 93', 'numero': 93}, {'distance': 8, 'nom': 'Hôpital des Alouettes 42', 'numero': 42}], 18: [{'distance': 4, 'nom': 'Cité du Marché 84', 'numero': 84}, {'distance': 12, 'nom': 'Cité des Arts 60', 'numero': 60}, {'distance': 9, 'nom': 'Allée du Stade 20', 'numero': 20}, {'distance': 9, 'nom': 'Passage du Marché 35', 'numero': 35}, {'distance': 5, 'nom': 'Quai de la Tour 19', 'numero': 19}], 19: [{'distance': 11, 'nom': 'Boulevard des Fleurs 2', 'numero': 2}, {'distance': 5, 'nom': 'Jardin des Alouettes 18', 'numero': 18}, {'distance': 9, 'nom': 'Avenue des Sports 76', 'numero': 76}, {'distance': 8, 'nom': 'Passage de Verdun 53', 'numero': 53}, {'distance': 2, 'nom': 'Stade du Stade 48', 'numero': 48}, {'distance': 13, 'nom': 'Parc de la République 30', 'numero': 30}], 20: [{'distance': 9, 'nom': 'Jardin des Alouettes 18', 'numero': 18}, {'distance': 11, 'nom': 'Passage du Marché 21', 'numero': 21}], 21: [{'distance': 2, 'nom': 'Impasse de la Gare 7', 'numero': 7}, {'distance': 11, 'nom': 'Allée du Stade 20', 'numero': 20}, {'distance': 2, 'nom': 'Pont de la Montagne 89', 'numero': 89}, {'distance': 7, 'nom': 'Stade des Fleurs 56', 'numero': 56}, {'distance': 7, 'nom': 'Théâtre du Centre 78', 'numero': 78}], 22: [{'distance': 11, 'nom': 'Jardin des Tilleuls 12', 'numero': 12}, {'distance': 5, 'nom': 'Avenue du Stade 14', 'numero': 14}, {'distance': 12, 'nom': 'Hôpital des Écoles 69', 'numero': 69}, {'distance': 2, 'nom': 'Passage de la Fontaine 34', 'numero': 34}, {'distance': 11, 'nom': 'Hôpital des Alouettes 72', 'numero': 72}, {'distance': 15, 'nom': 'Pont de la Montagne 89', 'numero': 89}], 23: [{'distance': 5, 'nom': 'Rue de Verdun 100', 'numero': 100}, {'distance': 7, 'nom': 'Cité du Marché 84', 'numero': 84}, {'distance': 3, 'nom': 'Marché de Verdun 45', 'numero': 45}], 24: [{'distance': 3, 'nom': 'Allée de Verdun 94', 'numero': 94}, {'distance': 9, 'nom': 'Passage du Marché 35', 'numero': 35}, {'distance': 15, 'nom': 'Passage du Centre 66', 'numero': 66}, {'distance': 2, 'nom': 'Hôpital des Arts 99', 'numero': 99}], 25: [{'distance': 3, 'nom': 'Gare du Marché 83', 'numero': 83}, {'distance': 6, 'nom': 'Passage du Centre 66', 'numero': 66}, {'distance': 13, 'nom': 'Quai du Lac 79', 'numero': 79}, {'distance': 3, 'nom': 'École de Verdun 27', 'numero': 27}], 26: [{'distance': 11, 'nom': 'Cité des Écoles 10', 'numero': 10}, {'distance': 8, 'nom': 'Théâtre du Centre 78', 'numero': 78}, {'distance': 1, 'nom': 'Place de la Gare 43', 'numero': 43}], 27: [{'distance': 11, 'nom': 'Pont de la Montagne 5', 'numero': 5}, {'distance': 3, 'nom': 'Parc de Verdun 25', 'numero': 25}, {'distance': 4, 'nom': 'Stade du Stade 48', 'numero': 48}, {'distance': 1, 'nom': 'Square de la Rivière 41', 'numero': 41}], 28: [{'distance': 15, 'nom': 'Jardin des Tilleuls 12', 'numero': 12}, {'distance': 8, 'nom': 'Rue de la Liberté 74', 'numero': 74}, {'distance': 14, 'nom': 'Allée des Tilleuls 95', 'numero': 95}], 29: [{'distance': 9, 'nom': 'Théâtre de la République 4', 'numero': 4}, {'distance': 7, 'nom': 'Impasse de la Gare 7', 'numero': 7}, {'distance': 13, 'nom': 'Hôpital des Arts 99', 'numero': 99}, {'distance': 3, 'nom': 'Place de la Montagne 70', 'numero': 70}], 30: [{'distance': 13, 'nom': 'Marché des Sports 6', 'numero': 6}, {'distance': 13, 'nom': 'Quai de la Tour 19', 'numero': 19}, {'distance': 3, 'nom': 'Marché des Alouettes 86', 'numero': 86}, {'distance': 5, 'nom': 'Pont de Verdun 62', 'numero': 62}, {'distance': 9, 'nom': 'Hôpital des Alouettes 72', 'numero': 72}], 31: [{'distance': 10, 'nom': 'Théâtre de la République 4', 'numero': 4}, {'distance': 8, 'nom': 'Théâtre du Centre 11', 'numero': 11}, {'distance': 4, 'nom': 'Pont de la Rivière 71', 'numero': 71}, {'distance': 12, 'nom': 'École du Marché 98', 'numero': 98}, {'distance': 5, 'nom': 'Allée des Tilleuls 95', 'numero': 95}, {'distance': 7, 'nom': 'Cité du Centre 90', 'numero': 90}], 32: [{'distance': 4, 'nom': 'Hôpital de la Liberté 58', 'numero': 58}, {'distance': 4, 'nom': 'Pont du Lac 68', 'numero': 68}, {'distance': 2, 'nom': 'Théâtre du Stade 59', 'numero': 59}], 33: [{'distance': 10, 'nom': 'Hôpital de la Gare 77', 'numero': 77}, {'distance': 4, 'nom': 'Hôpital des Alouettes 72', 'numero': 72}], 34: [{'distance': 2, 'nom': 'Stade de la Rivière 22', 'numero': 22}, {'distance': 11, 'nom': 'Impasse de la Paix 92', 'numero': 92}], 35: [{'distance': 9, 'nom': 'Théâtre de Verdun 8', 'numero': 8}, {'distance': 9, 'nom': 'Jardin des Alouettes 18', 'numero': 18}, {'distance': 9, 'nom': 'Théâtre de la Liberté 24', 'numero': 24}], 36: [{'distance': 9, 'nom': 'Pont de Verdun 44', 'numero': 44}], 37: [{'distance': 12, 'nom': 'Marché des Sports 6', 'numero': 6}, {'distance': 2, 'nom': 'Impasse de la Gare 7', 'numero': 7}, {'distance': 4, 'nom': 'École des Arts 87', 'numero': 87}, {'distance': 9, 'nom': 'Pont de la République 64', 'numero': 64}], 38: [{'distance': 4, 'nom': 'Allée de Verdun 94', 'numero': 94}, {'distance': 13, 'nom': 'Hôpital des Écoles 75', 'numero': 75}, {'distance': 8, 'nom': 'Pont de Verdun 62', 'numero': 62}], 39: [{'distance': 7, 'nom': 'Marché des Alouettes 86', 'numero': 86}, {'distance': 7, 'nom': 'Impasse de la Paix 57', 'numero': 57}, {'distance': 8, 'nom': 'Jardin de la Rivière 47', 'numero': 47}], 40: [{'distance': 11, 'nom': 'Théâtre de la Tour 88', 'numero': 88}, {'distance': 2, 'nom': 'Square du Stade 85', 'numero': 85}], 41: [{'distance': 1, 'nom': 'École de Verdun 27', 'numero': 27}, {'distance': 6, 'nom': 'Passage de Verdun 53', 'numero': 53}, {'distance': 13, 'nom': 'Allée des Tilleuls 95', 'numero': 95}], 42: [{'distance': 5, 'nom': 'Gare de la Rivière 16', 'numero': 16}, {'distance': 8, 'nom': 'Boulevard de la Tour 17', 'numero': 17}], 43: [{'distance': 1, 'nom': 'Parc de la République 15', 'numero': 15}, {'distance': 1, 'nom': 'Avenue de la Liberté 26', 'numero': 26}, {'distance': 7, 'nom': 'Place de la Montagne 70', 'numero': 70}, {'distance': 3, 'nom': 'Théâtre du Stade 59', 'numero': 59}], 44: [{'distance': 9, 'nom': 'Passage des Tilleuls 36', 'numero': 36}, {'distance': 13, 'nom': 'Boulevard de la Paix 61', 'numero': 61}, {'distance': 14, 'nom': 'Hôpital de la Liberté 58', 'numero': 58}], 45: [{'distance': 6, 'nom': 'Impasse de la Gare 7', 'numero': 7}, {'distance': 3, 'nom': 'École de la Tour 23', 'numero': 23}, {'distance': 9, 'nom': 'Square du Stade 85', 'numero': 85}], 46: [{'distance': 12, 'nom': 'Théâtre de Verdun 8', 'numero': 8}, {'distance': 14, 'nom': 'École du Marché 98', 'numero': 98}], 47: [{'distance': 12, 'nom': 'Jardin des Tilleuls 12', 'numero': 12}, {'distance': 8, 'nom': 'Square de la Tour 39', 'numero': 39}, {'distance': 8, 'nom': 'Boulevard de la Paix 54', 'numero': 54}, {'distance': 4, 'nom': 'Pont de la République 64', 'numero': 64}], 48: [{'distance': 2, 'nom': 'Quai de la Tour 19', 'numero': 19}, {'distance': 4, 'nom': 'École de Verdun 27', 'numero': 27}, {'distance': 5, 'nom': 'Stade de la Fontaine 50', 'numero': 50}, {'distance': 15, 'nom': 'Jardin des Alouettes 51', 'numero': 51}], 49: [{'distance': 5, 'nom': 'Jardin des Tilleuls 12', 'numero': 12}, {'distance': 11, 'nom': 'Stade des Fleurs 56', 'numero': 56}, {'distance': 12, 'nom': 'Cité des Écoles 91', 'numero': 91}, {'distance': 8, 'nom': 'Allée des Tilleuls 95', 'numero': 95}, {'distance': 3, 'nom': 'Parc des Fleurs 73', 'numero': 73}], 50: [{'distance': 9, 'nom': 'Boulevard des Arts 9', 'numero': 9}, {'distance': 14, 'nom': 'Théâtre du Centre 11', 'numero': 11}, {'distance': 11, 'nom': 'Avenue du Stade 14', 'numero': 14}, {'distance': 5, 'nom': 'Stade du Stade 48', 'numero': 48}], 51: [{'distance': 15, 'nom': 'Stade du Stade 48', 'numero': 48}, {'distance': 1, 'nom': 'Place de la Tour 97', 'numero': 97}], 52: [{'distance': 9, 'nom': 'Avenue des Sports 76', 'numero': 76}, {'distance': 15, 'nom': 'Jardin des Fleurs 63', 'numero': 63}], 53: [{'distance': 2, 'nom': 'Gare de la Rivière 16', 'numero': 16}, {'distance': 8, 'nom': 'Quai de la Tour 19', 'numero': 19}, {'distance': 6, 'nom': 'Square de la Rivière 41', 'numero': 41}, {'distance': 14, 'nom': 'Rue des Tilleuls 67', 'numero': 67}], 54: [{'distance': 8, 'nom': 'Jardin de la Rivière 47', 'numero': 47}, {'distance': 14, 'nom': 'Théâtre du Centre 78', 'numero': 78}, {'distance': 4, 'nom': 'Théâtre de la Tour 88', 'numero': 88}], 55: [{'distance': 1, 'nom': 'Rue de la Liberté 74', 'numero': 74}, {'distance': 10, 'nom': 'Avenue des Sports 76', 'numero': 76}, {'distance': 2, 'nom': 'Théâtre du Centre 78', 'numero': 78}], 56: [{'distance': 1, 'nom': 'Pont des Écoles 3', 'numero': 3}, {'distance': 7, 'nom': 'Passage du Marché 21', 'numero': 21}, {'distance': 11, 'nom': 'Jardin de la Tour 49', 'numero': 49}, {'distance': 15, 'nom': 'Marché des Alouettes 86', 'numero': 86}, {'distance': 5, 'nom': 'Avenue des Sports 76', 'numero': 76}, {'distance': 4, 'nom': 'Rue de la Liberté 74', 'numero': 74}, {'distance': 11, 'nom': 'Pont du Lac 68', 'numero': 68}], 57: [{'distance': 7, 'nom': 'Square de la Tour 39', 'numero': 39}], 58: [{'distance': 4, 'nom': 'Allée de la Rivière 32', 'numero': 32}, {'distance': 14, 'nom': 'Pont de Verdun 44', 'numero': 44}, {'distance': 1, 'nom': 'Cité des Arts 60', 'numero': 60}, {'distance': 8, 'nom': 'École du Marché 98', 'numero': 98}], 59: [{'distance': 13, 'nom': 'Marché des Sports 6', 'numero': 6}, {'distance': 2, 'nom': 'Allée de la Rivière 32', 'numero': 32}, {'distance': 3, 'nom': 'Place de la Gare 43', 'numero': 43}, {'distance': 4, 'nom': 'Place de la Montagne 70', 'numero': 70}], 60: [{'distance': 12, 'nom': 'Jardin des Alouettes 18', 'numero': 18}, {'distance': 1, 'nom': 'Hôpital de la Liberté 58', 'numero': 58}], 61: [{'distance': 15, 'nom': 'Avenue du Stade 14', 'numero': 14}, {'distance': 13, 'nom': 'Pont de Verdun 44', 'numero': 44}, {'distance': 12, 'nom': 'Pont de la Rivière 71', 'numero': 71}], 62: [{'distance': 5, 'nom': 'Parc de la République 30', 'numero': 30}, {'distance': 8, 'nom': 'Impasse de la Gare 38', 'numero': 38}, {'distance': 11, 'nom': 'Théâtre des Arts 80', 'numero': 80}, {'distance': 14, 'nom': 'Square du Stade 85', 'numero': 85}, {'distance': 9, 'nom': 'Hôpital des Écoles 69', 'numero': 69}], 63: [{'distance': 15, 'nom': 'Passage des Arts 52', 'numero': 52}, {'distance': 2, 'nom': 'Marché des Alouettes 86', 'numero': 86}], 64: [{'distance': 9, 'nom': 'Place du Stade 37', 'numero': 37}, {'distance': 4, 'nom': 'Jardin de la Rivière 47', 'numero': 47}, {'distance': 3, 'nom': 'Place de la Tour 97', 'numero': 97}, {'distance': 5, 'nom': 'Hôpital des Alouettes 72', 'numero': 72}], 65: [{'distance': 4, 'nom': 'Quai du Lac 79', 'numero': 79}, {'distance': 11, 'nom': 'Passage de la Gare 93', 'numero': 93}], 66: [{'distance': 15, 'nom': 'Théâtre de la Liberté 24', 'numero': 24}, {'distance': 6, 'nom': 'Parc de Verdun 25', 'numero': 25}], 67: [{'distance': 14, 'nom': 'Passage de Verdun 53', 'numero': 53}, {'distance': 14, 'nom': 'Gare du Marché 83', 'numero': 83}], 68: [{'distance': 4, 'nom': 'Allée de la Rivière 32', 'numero': 32}, {'distance': 11, 'nom': 'Stade des Fleurs 56', 'numero': 56}, {'distance': 3, 'nom': 'Rue de Verdun 100', 'numero': 100}], 69: [{'distance': 12, 'nom': 'Stade de la Rivière 22', 'numero': 22}, {'distance': 9, 'nom': 'Pont de Verdun 62', 'numero': 62}, {'distance': 12, 'nom': 'Avenue des Fleurs 96', 'numero': 96}, {'distance': 7, 'nom': 'Hôpital des Alouettes 72', 'numero': 72}], 70: [{'distance': 3, 'nom': 'Cité des Sports 29', 'numero': 29}, {'distance': 7, 'nom': 'Place de la Gare 43', 'numero': 43}, {'distance': 4, 'nom': 'Théâtre du Stade 59', 'numero': 59}], 71: [{'distance': 4, 'nom': 'Hôpital de la Fontaine 31', 'numero': 31}, {'distance': 12, 'nom': 'Boulevard de la Paix 61', 'numero': 61}], 72: [{'distance': 11, 'nom': 'Stade de la Rivière 22', 'numero': 22}, {'distance': 9, 'nom': 'Parc de la République 30', 'numero': 30}, {'distance': 4, 'nom': 'Impasse du Château 33', 'numero': 33}, {'distance': 5, 'nom': 'Pont de la République 64', 'numero': 64}, {'distance': 7, 'nom': 'Hôpital des Écoles 69', 'numero': 69}], 73: [{'distance': 12, 'nom': 'Pont de la Montagne 5', 'numero': 5}, {'distance': 3, 'nom': 'Jardin de la Tour 49', 'numero': 49}], 74: [{'distance': 4, 'nom': 'Boulevard de la Tour 17', 'numero': 17}, {'distance': 8, 'nom': 'École de la Montagne 28', 'numero': 28}, {'distance': 1, 'nom': 'Parc des Écoles 55', 'numero': 55}, {'distance': 4, 'nom': 'Stade des Fleurs 56', 'numero': 56}, {'distance': 13, 'nom': 'École des Arts 87', 'numero': 87}], 75: [{'distance': 1, 'nom': 'Cité des Écoles 10', 'numero': 10}, {'distance': 13, 'nom': 'Impasse de la Gare 38', 'numero': 38}, {'distance': 13, 'nom': 'Avenue de Verdun 81', 'numero': 81}, {'distance': 13, 'nom': 'Place de la Tour 97', 'numero': 97}], 76: [{'distance': 9, 'nom': 'Quai de la Tour 19', 'numero': 19}, {'distance': 9, 'nom': 'Passage des Arts 52', 'numero': 52}, {'distance': 10, 'nom': 'Parc des Écoles 55', 'numero': 55}, {'distance': 5, 'nom': 'Stade des Fleurs 56', 'numero': 56}], 77: [{'distance': 1, 'nom': 'Pont des Écoles 3', 'numero': 3}, {'distance': 3, 'nom': 'Marché des Sports 6', 'numero': 6}, {'distance': 10, 'nom': 'Impasse du Château 33', 'numero': 33}, {'distance': 5, 'nom': 'École des Arts 87', 'numero': 87}, {'distance': 3, 'nom': 'Avenue des Fleurs 96', 'numero': 96}], 78: [{'distance': 7, 'nom': 'Passage du Marché 21', 'numero': 21}, {'distance': 8, 'nom': 'Avenue de la Liberté 26', 'numero': 26}, {'distance': 14, 'nom': 'Boulevard de la Paix 54', 'numero': 54}, {'distance': 2, 'nom': 'Parc des Écoles 55', 'numero': 55}], 79: [{'distance': 8, 'nom': 'Théâtre de Verdun 8', 'numero': 8}, {'distance': 3, 'nom': 'Gare du Château 13', 'numero': 13}, {'distance': 13, 'nom': 'Parc de Verdun 25', 'numero': 25}, {'distance': 4, 'nom': 'Stade du Lac 65', 'numero': 65}], 80: [{'distance': 11, 'nom': 'Pont de Verdun 62', 'numero': 62}, {'distance': 4, 'nom': 'Marché des Alouettes 86', 'numero': 86}], 81: [{'distance': 13, 'nom': 'Hôpital des Écoles 75', 'numero': 75}, {'distance': 11, 'nom': 'Rue de Verdun 100', 'numero': 100}], 82: [{'distance': 15, 'nom': 'Théâtre de la Tour 88', 'numero': 88}], 83: [{'distance': 9, 'nom': 'Gare du Château 13', 'numero': 13}, {'distance': 3, 'nom': 'Parc de Verdun 25', 'numero': 25}, {'distance': 14, 'nom': 'Rue des Tilleuls 67', 'numero': 67}], 84: [{'distance': 4, 'nom': 'Jardin des Alouettes 18', 'numero': 18}, {'distance': 7, 'nom': 'École de la Tour 23', 'numero': 23}], 85: [{'distance': 2, 'nom': 'Hôpital des Tilleuls 40', 'numero': 40}, {'distance': 9, 'nom': 'Marché de Verdun 45', 'numero': 45}, {'distance': 14, 'nom': 'Pont de Verdun 62', 'numero': 62}, {'distance': 9, 'nom': 'Allée des Tilleuls 95', 'numero': 95}], 86: [{'distance': 3, 'nom': 'Parc de la République 30', 'numero': 30}, {'distance': 7, 'nom': 'Square de la Tour 39', 'numero': 39}, {'distance': 15, 'nom': 'Stade des Fleurs 56', 'numero': 56}, {'distance': 2, 'nom': 'Jardin des Fleurs 63', 'numero': 63}, {'distance': 4, 'nom': 'Théâtre des Arts 80', 'numero': 80}], 87: [{'distance': 4, 'nom': 'Place du Stade 37', 'numero': 37}, {'distance': 13, 'nom': 'Rue de la Liberté 74', 'numero': 74}, {'distance': 5, 'nom': 'Hôpital de la Gare 77', 'numero': 77}, {'distance': 7, 'nom': 'Impasse de la Paix 92', 'numero': 92}], 88: [{'distance': 11, 'nom': 'Hôpital des Tilleuls 40', 'numero': 40}, {'distance': 4, 'nom': 'Boulevard de la Paix 54', 'numero': 54}, {'distance': 15, 'nom': 'Boulevard des Tilleuls 82', 'numero': 82}], 89: [{'distance': 13, 'nom': 'Parc de la République 15', 'numero': 15}, {'distance': 2, 'nom': 'Passage du Marché 21', 'numero': 21}, {'distance': 15, 'nom': 'Stade de la Rivière 22', 'numero': 22}], 90: [{'distance': 7, 'nom': 'Hôpital de la Fontaine 31', 'numero': 31}], 91: [{'distance': 12, 'nom': 'Jardin de la Tour 49', 'numero': 49}], 92: [{'distance': 4, 'nom': 'Cité des Écoles 10', 'numero': 10}, {'distance': 11, 'nom': 'Passage de la Fontaine 34', 'numero': 34}, {'distance': 7, 'nom': 'École des Arts 87', 'numero': 87}], 93: [{'distance': 11, 'nom': 'Boulevard de la Tour 17', 'numero': 17}, {'distance': 11, 'nom': 'Stade du Lac 65', 'numero': 65}], 94: [{'distance': 3, 'nom': 'Théâtre de la Liberté 24', 'numero': 24}, {'distance': 4, 'nom': 'Impasse de la Gare 38', 'numero': 38}, {'distance': 5, 'nom': 'Place de la Tour 97', 'numero': 97}], 95: [{'distance': 14, 'nom': 'École de la Montagne 28', 'numero': 28}, {'distance': 5, 'nom': 'Hôpital de la Fontaine 31', 'numero': 31}, {'distance': 13, 'nom': 'Square de la Rivière 41', 'numero': 41}, {'distance': 8, 'nom': 'Jardin de la Tour 49', 'numero': 49}, {'distance': 9, 'nom': 'Square du Stade 85', 'numero': 85}], 96: [{'distance': 4, 'nom': 'Cité du Marché 1', 'numero': 1}, {'distance': 12, 'nom': 'Boulevard des Fleurs 2', 'numero': 2}, {'distance': 12, 'nom': 'Hôpital des Écoles 69', 'numero': 69}, {'distance': 3, 'nom': 'Hôpital de la Gare 77', 'numero': 77}], 97: [{'distance': 1, 'nom': 'Jardin des Alouettes 51', 'numero': 51}, {'distance': 3, 'nom': 'Pont de la République 64', 'numero': 64}, {'distance': 13, 'nom': 'Hôpital des Écoles 75', 'numero': 75}, {'distance': 5, 'nom': 'Allée de Verdun 94', 'numero': 94}], 98: [{'distance': 12, 'nom': 'Hôpital de la Fontaine 31', 'numero': 31}, {'distance': 14, 'nom': 'Pont de la Montagne 46', 'numero': 46}, {'distance': 8, 'nom': 'Hôpital de la Liberté 58', 'numero': 58}], 99: [{'distance': 2, 'nom': 'Impasse de la Gare 7', 'numero': 7}, {'distance': 2, 'nom': 'Théâtre de la Liberté 24', 'numero': 24}, {'distance': 13, 'nom': 'Cité des Sports 29', 'numero': 29}], 100: [{'distance': 4, 'nom': 'Parc de la République 15', 'numero': 15}, {'distance': 5, 'nom': 'École de la Tour 23', 'numero': 23}, {'distance': 3, 'nom': 'Pont du Lac 68', 'numero': 68}, {'distance': 11, 'nom': 'Avenue de Verdun 81', 'numero': 81}]} #################################################################################################### #################### # Question 1 # 2 points #################### arrets[101]="Stade Olympique 101" graphe[101]=[{'distance': 8, 'nom': 'Cité du Marché 1', 'numero': 1}, {'distance': 12, 'nom': 'Pont de la Montagne 5', 'numero': 5}] graphe[1].append({'distance': 8, 'nom': 'Stade Olympique 101', 'numero': 101}) graphe[5].append({'distance': 12, 'nom': 'Stade Olympique 101', 'numero': 101}) #################### # Question 2 # 1 point #################### def verifier_numerotation(arrets) : L=list(arrets.keys()) L.sort() return L==[k for k in range(1,102)] #################### # Question 3 # #################### #3a : Correction de la fonction de vérification # 1 point def est_connexe_depuis(graphe, arret_depart) : if arret_depart in graphe: visites = [] pile = [arret_depart] while pile: arret = pile.pop() if arret not in visites: visites.append(arret) for voisin in graphe[arret]: pile.append(voisin['numero']) return len(visites) == len(graphe) else: return False # Exemple de graphe pour les tests graphe_test = { 1: [{'numero': 2, 'nom': 'Arrêt 2', 'distance': 5}], 2: [{'numero': 1, 'nom': 'Arrêt 1', 'distance': 5}, {'numero': 1, 'nom': 'Arrêt 1', 'distance': 7}, {'numero': 3, 'nom': 'Arrêt 3', 'distance': 10}], 3: [] } # Série d'asserts pour montrer que la fonction ne fonctionne pas assert est_connexe_depuis(graphe_test, 2) == True assert est_connexe_depuis(graphe_test, 1) == True assert est_connexe_depuis(graphe_test, 102) == False assert est_connexe_depuis(graphe_test, 3) == False #3b 1,5 points #Votre réponse : result=True for a in arrets.keys(): if not est_connexe_depuis(graphe, a): result=False print(result) #################### # Question 4 # #################### def plus_court_chemin(graphe, arret_depart, arret_arrivee): # Initialisation des distances et des prédécesseurs distances = {arret: float('inf') for arret in graphe} distances[arret_depart] = 0 predecesseurs = {arret: None for arret in graphe} # Liste des arrêts à visiter a_visiter = [] for arret in graphe: a_visiter.append(arret) while a_visiter: # Trouver l'arrêt avec la plus petite distance non visitée arret_actuel = a_visiter[0] min_distance = distances[arret_actuel] for arret in a_visiter: if distances[arret] < min_distance: arret_actuel = arret min_distance = distances[arret] a_visiter.remove(arret_actuel) # Si on a atteint l'arrêt d'arrivée, reconstruire le chemin if arret_actuel == arret_arrivee: chemin = [] current = arret_actuel while current is not None: chemin.insert(0, current) # On ajoute l'arrêt au début de la liste pour obtenir le chemin dans le bon ordre current = predecesseurs[current] # On remonte au prédécesseur return (distances[arret_arrivee], chemin) # Retourne la distance totale et le chemin # Mettre à jour les distances des voisins for voisin in graphe[arret_actuel]: nouvelle_distance = distances[arret_actuel] + voisin['distance'] if nouvelle_distance < distances[voisin['numero']]: distances[voisin['numero']] = nouvelle_distance predecesseurs[voisin['numero']] = arret_actuel # Si on sort de la boucle sans avoir trouvé l'arrêt d'arrivée, retourner une distance infinie et un chemin vide return (float('inf'), []) # implémentation du graphe pour les tests graphe_test = { 1: [ {'numero': 2, 'nom': 'Arrêt 2', 'distance': 4}, {'numero': 3, 'nom': 'Arrêt 3', 'distance': 6}, {'numero': 5, 'nom': 'Arrêt 5', 'distance': 1} ], 2: [ {'numero': 1, 'nom': 'Arrêt 1', 'distance': 4}, {'numero': 4, 'nom': 'Arrêt 4', 'distance': 5} ], 3: [ {'numero': 1, 'nom': 'Arrêt 1', 'distance': 6}, {'numero': 5, 'nom': 'Arrêt 5', 'distance': 1} ], 4: [{'numero': 3, 'nom': 'Arrêt 3', 'distance': 7} ], 5: [ {'numero': 1, 'nom': 'Arrêt 1', 'distance': 1}, {'numero': 3, 'nom': 'Arrêt 3', 'distance': 1} ] } #4a Tester cette fonction entre les arrêts 4 et 2 # 1 points print(plus_court_chemin(graphe_test, 4, 2)) print(plus_court_chemin(graphe, 4, 2)) #Votre réponse : #4b : 3 assertions # 1,5 points assert plus_court_chemin(graphe_test, 1, 4) == (9, [1, 2, 4]) assert plus_court_chemin(graphe_test, 5, 4) == (10, [5, 1, 2, 4]) assert plus_court_chemin(graphe_test, 4, 2) == (13, [4, 3, 5, 1, 2]) #Votre réponse : #4c : l'arrêt le plus loin # 2 points #Votre réponse : loin=(1,[]) for a in arrets.keys(): tmp=plus_court_chemin(graphe, 1, a) if tmp[0]>loin[0]: loin=tmp print(loin)