Cómo funciona el camino más corto

Cada línea tiene una longitud distinta

Ya sabes unir puntos con líneas. Pero los caminos reales tienen algo más: cada línea tiene una longitud distinta.
Unos caminos son cortos y otros largos, así que escribimos un número sobre cada línea. Ese número es la distancia.
Toca los caminos de abajo para ver sus distancias.

Toca un camino para ver su distancia. (línea = camino · número = distancia de ese camino)

¿Por qué importa que las distancias sean distintas? Incluso una ruta que pasa por menos cruces puede ser más lenta en total si cada tramo es largo.
Y al revés, una ruta que pasa por más cruces puede ser más rápida en total si cada tramo es corto.
Así que no se puede elegir un camino dejando fuera la distancia.

Contar pasos por cercanía no basta

Antes vimos el método que se extiende de lo más cercano a lo más lejano: un paso, dos pasos, tres pasos, contando a cuántos pasos de la salida está cada punto.
Pero eso solo vale cuando todos los caminos miden exactamente un paso.
Si cada camino mide distinto, la ruta con menos pasos no tiene por qué ser la más cercana.

Toca las dos rutas para compararlas. (menos pasos vs distancia más corta · no son lo mismo)

La ruta con menos cruces resultó ser más larga en distancia. Si solo cuentas pasos, caes en esta trampa.
Por eso, en vez de contar pasos, hay que ir sumando distancias para encontrar el camino de verdad más cercano.

Fijar primero lo más cercano

¿Y qué hacemos? Recuerda el método voraz, que elige lo mejor que tiene delante.
Empezando por la salida, entre los puntos cuya distancia aún no está fijada, eliges el que está más cerca ahora mismo y fijas su distancia.
Mientras ningún camino tenga longitud negativa, no puede haber un camino más corto hasta el punto más cercano, así que fijarlo es seguro.

Toca el punto más cercano para fijarlo. (cada vez, elige el punto sin fijar con la distancia más corta)

Esto es elegir lo mejor de cada momento. En vez de resolver el mapa entero, vas fijando puntos uno a uno, empezando por el más cercano.
Al fijar un punto, los vecinos que se alcanzan pasando por él pueden quedar más cerca.
Este método se llama algoritmo de Dijkstra.

Ensanchar la frontera

A medida que fijas más puntos, se forma una «región de distancias fijadas», y su borde es la frontera.
Cada vez que incorporas el punto más cercano justo fuera de la frontera, la región crece un punto.
Es como las ondas que se extienden al tirar una piedra en agua quieta.

Toca un punto justo fuera de la frontera para ampliar la región. (la región fijada crece hacia fuera de punto en punto)

A medida que la frontera se extiende hacia fuera, al final todos los puntos quedan dentro de la región fijada.
Para entonces ya conoces la distancia más rápida desde la salida hasta cualquier punto. Primero lo cercano, paso a paso: ese es el secreto.

Resumen

La búsqueda del camino más rápido, en una línea: cuando cada línea mide distinto, la ruta con menos pasos no es necesariamente la más rápida, así que contar pasos por cercanía no basta.
Si fijas distancias empezando por el punto más cercano y ensanchas la frontera de punto en punto, eligiendo en cada momento lo mejor que tienes delante, encuentras la distancia más corta hasta todos los puntos.

Toca los puntos clave en orden para resumir. (las distancias difieren → contar pasos falla → fijar primero lo más cercano → ensanchar la frontera)

Cuando una aplicación de mapas encuentra el camino más rápido, por dentro ocurre esto: fija distancias empezando por los lugares más cercanos y va ensanchando la frontera poco a poco.
La sencilla regla de quedarse con lo mejor de cada momento trae la respuesta más rápida incluso en caminos complicados donde cada distancia es distinta.