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 moins un tronçon d’écart). À chaque point de la carte, il y a au moins 3 tronçons qui se rejoignent. Cela commence à l’origine, avec 3 possibilités puis à chaque point rencontré, avec au moins 2 tronçons possibles pour poursuivre un chemin. Ainsi, les chemins qui passent par k points sont au moins au nombre de 2 *k, chacun pouvant potentiellement être le plus rapide pour rallier la destination B. Et ce nombre k est inconnu. Il faut ainsi explorer les chemins à 2, 3, 4… étapes. Même s’il est rare qu’un chemin comportant un grand nombre de points soit le plus rapide, ce n’est théoriquement pas impossible : il faut donc énumérer tous les nombres de points entre 1 et n – 2 où n* est le nombre total de points de la carte. Cette quantité exponentielle de chemins est donc égale à :
