Observemos un mapa de carreteras o de transporte público. Podemos describirlo como un conjunto de tramos de carretera que conectan puntos: todos esos puntos son bifurcaciones, como cruces o interconexiones. El tiempo de recorrido de cada tramo no es proporcional a su longitud: puede tratarse de una autopista o de un camino de montaña; podemos alternar trayectos a pie, en tren, en coche o en metro…
Así, a veces hay que partir hacia el este para tomar un tren rápido que nos lleve más al oeste. En el mapa de arriba, ¿el camino más rápido de A a B consiste en tomar la carretera secundaria roja que los une o la autopista azul?
Enumeración de caminos ------------------------
De forma más general, examinemos los caminos posibles entre un punto de origen A y un punto de destino B. Para encontrar un camino rápido, una primera idea consiste en enumerar todos los caminos posibles que parten de A. El objetivo es determinar cuáles llegan a B y, entre ellos, uno que sea el más rápido. Para evaluar si esta enumeración es posible, debemos preguntarnos cuántos caminos diferentes parten de A (es decir, caminos que difieren en al menos un tramo). En cada punto del mapa confluyen al menos 3 tramos. Esto empieza en el origen, con 3 posibilidades, y continúa en cada punto encontrado, con al menos 2 tramos posibles para proseguir un camino. Así, los caminos que pasan por k puntos son al menos 2 *k, y cada uno puede ser potencialmente el más rápido para llegar al destino B. Y este número k es desconocido. Por tanto, hay que explorar los caminos de 2, 3, 4… etapas. Aunque es raro que un camino con un gran número de puntos sea el más rápido, no es teóricamente imposible: por ello hay que enumerar todos los números de puntos entre 1 y n – 2, donde n* es el número total de puntos del mapa. Esta cantidad exponencial de caminos es, por tanto, igual a: