Hallar el camino más rápido

Cada arista tiene su distancia

Ya aprendiste a unir punto con punto por una línea.
Pero las calles tienen algo más.
Cada arista tiene distinta distancia.
Unas calles son cortas,
otras lejanas.
Por eso escribimos un número en la línea.
Ese número es la distancia.
Abajo, toca una calle para ver su distancia.

Toca una calle para ver su distancia. (Línea = calle · número = su distancia)

¿Por qué importa que la distancia varíe?
Aunque una ruta pase por menos cruces,
si cada salto es lejano,
puede ser más lenta en total.
Al revés, más cruces
pero cada salto cercano,
puede ser más rápida en total.
Así que no puedes elegir camino sin la distancia.

Solo por cercanía no basta

Antes viste expandirse por cercanía.
Un salto, dos, tres,
contando cuántos saltos desde el inicio.
Pero eso vale cuando cada calle
es el mismo único salto.
Cuando las aristas tienen distintas distancias,
la ruta con menos saltos
no siempre es la más cercana.

Toca ambas rutas para comparar. (Menos saltos vs menor distancia · no es lo mismo)

¿Ves? La ruta con menos cruces
era más lejana en distancia.
Cuenta solo saltos,
y caes en esta trampa.
Por eso tenemos que
sumar distancias,
no saltos,
para hallar el camino de verdad más cercano.

Fija primero lo más cercano

¿Entonces qué hacemos?
Recuerda elegir lo mejor que tienes delante.
Empieza desde el inicio,
y entre los puntos sin distancia fijada,
elige el más cercano ahora mismo
y fija su distancia.
El punto más cercano
no puede tener un camino más corto,
así que fijarlo es seguro.

Toca el punto más cercano para fijarlo. (Cada vuelta elige el más corto entre los no fijados)

Esto es elegir lo mejor que está delante.
No resolver el mapa entero de golpe,
sino desde el punto más cercano ahora,
fijarlos uno a uno.
Al fijar un punto,
sus vecinos alcanzados por él
pueden conseguir una distancia
nueva y más cercana.

Ensancha la frontera

A medida que crecen los puntos fijados,
se forma una zona de distancias resueltas.
El borde de esa zona es la frontera.
Cada vez, justo fuera de la frontera,
metes el punto más cercano,
y la zona crece un punto.
Como tirar una piedra en agua quieta
y la onda extenderse.

Toca un punto tras la frontera para crecer la zona. (La zona fijada crece hacia afuera un punto cada vez)

Mientras la frontera sigue extendiéndose,
tarde o temprano cada punto
entra en la zona fijada.
Para entonces, desde el inicio
hasta cualquier punto,
sabes la distancia más rápida
de todos.
El más cercano primero, paso a paso, ese es el truco.

Cierre

Reunamos hallar el camino más rápido en una línea.
Si las aristas difieren en distancia,
menos saltos no es la ruta rápida.
Por eso contar solo por cercanía se queda corto.
Fija distancias desde el punto más cercano
y ensancha la frontera un punto cada vez,
y eligiendo lo mejor delante en cada momento,
hallas la distancia más corta a cada punto.

Haz clic en los puntos clave en orden para cerrar. (Distancia difiere → saltos no bastan → fija el más cercano → ensancha la frontera)

Cuando una app de mapas te halla el camino más rápido,
esto es lo que pasa dentro.
Fijar distancias desde los lugares cercanos
y ensanchar la frontera poco a poco.
Una regla simple, lo mejor delante,
aun en calles enredadas de toda distancia,
te trae la respuesta más rápida.