{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 2A.algo - Parcourir les rues de Paris\n", "\n", "Algorithme de plus courts chemins dans un graphe. Calcul d'un chemin compar\u00e9 au calcul de tous les chemins les plus courts."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["Populating the interactive namespace from numpy and matplotlib\n"]}], "source": ["%matplotlib inline"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Cette id\u00e9e vient d'une soir\u00e9e Google Code initi\u00e9e par Google et \u00e0 laquelle des \u00e9l\u00e8ves de l'ENSAE ont particip\u00e9. On dispose de la description des rues de Paris (qu'on consid\u00e8rera comme des lignes droites). On veut d\u00e9terminer le trajet de huit voitures de telle sorte qu'elles parcourent la ville le plus rapidement possible. On supposera deux cas :\n", "\n", "- Les voitures peuvent \u00eatre plac\u00e9es n'importe o\u00f9 dans la ville.\n", "- Les voitures d\u00e9marrent et reviennent au m\u00eame point de d\u00e9part, le m\u00eame pour toutes.\n", "\n", "Ce notebook d\u00e9crit comment r\u00e9cup\u00e9rer les donn\u00e9es et propose une solution. Ce probl\u00e8me est plus connu sous le nom du [probl\u00e8me du postier chinois](https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois) ou [Route inspection problem](https://en.wikipedia.org/wiki/Route_inspection_problem) pour lequel il existe un algorithme optimal \u00e0 co\u00fbt polynomial. Le probl\u00e8me n'est donc pas [NP complet](https://en.wikipedia.org/wiki/NP-completeness)."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"text/html": ["
\n", ""], "text/plain": ["