Observons une carte routière ou une carte de transports publics. On peut la décrire comme un ensemble de tronçons de routes reliant des points : ces points sont tous des embranchements, comme des carrefours ou des interconnexions. Le temps de transport pour chaque tronçon n’est pas proportionnel à sa longueur : il peut s’agir d’une autoroute ou d’un chemin de montagne, on peut alterner les parcours à pied, en train, en voiture, en métro…
Ainsi, il faut parfois partir vers l’est pour prendre un train rapide qui nous amènera plus à l’ouest. Dans la carte ci-dessus, le chemin le plus rapide pour aller de A à B est-il de prendre la départementale rouge qui les relie ou l’autoroute en bleu ?
Énumération des chemins
Plus généralement, regardons les chemins possibles entre un point origine A et un point destination B. Pour trouver un chemin rapide, une première idée est d’énumérer tous les chemins possibles partant de A. Le but est ainsi de déterminer ceux qui mènent à B et parmi eux, un qui soit le plus rapide. Pour juger si cette énumération est possible, on doit se demander combien il y a de chemins différents issus de A (c’est-à-dire des chemins ayant au ...
Lire la suite gratuitement