¿Cuál es la prueba intuitiva más simple del algoritmo de ruta más corta de Dijkstra?

La idea que me ayudó a comprender el algoritmo de Dijkstra fue que es básicamente una versión eficiente de búsqueda de amplitud en un gráfico diferente.

Específicamente, dado un gráfico G con pesos de borde enteros positivos, se podría construir un nuevo gráfico H no ponderado (con los mismos vértices en G y algunos adicionales), reemplazando cada borde ponderado con un número de bordes equivalente a su peso. Entonces, por ejemplo, si tuviera un borde (u, v) con un peso de 10 en G, reemplazaría este borde por una serie de 10 bordes entre u y v (con nuevos vértices intermedios, por supuesto) en H.

Ahora, las distancias entre los vértices que originalmente eran de G se conservan, pero hemos convertido el gráfico ponderado en un gráfico no ponderado en el que podemos ejecutar BFS.

En este punto, es posible que se dé cuenta de que realmente no le importan las distancias a estos nuevos vértices intermedios, y solo desearía poner en cola / visitar los vértices que originalmente eran de G, lo que lo lleva a la idea de una prioridad cola, y todas las cosas buenas que Anders ha discutido.

Y luego puede darse cuenta de que, aunque la construcción requirió pesos enteros, podría llegar a una prueba de que funciona de manera más general.

Felicidades, acabas de derivar el algoritmo de Dijkstra.

Podrías derivar el algoritmo por ti mismo. Encuentre la respuesta a las 2 preguntas siguientes.

Pregunta 1
Dado un gráfico dirigido de N, con bordes de pesos no negativos, y un nodo de inicio S, podría hacer lo siguiente:

• Encuentre un nodo con el menor costo de ruta más corto.

Por ejemplo, en el gráfico (1, 2) = 3, (1, 3) = 7, (1, 4) = 5, (2, 4) = 1, (3, 5) = 2, (4, 5) = 10

Dado inicio nodo 1?

• Como gráfico de 5 nodos, hay 4 costos de rutas más cortos de 1.
• Una respuesta es SP (1, 2) = 3

Pregunta 2
Dado un gráfico dirigido de N, con bordes de pesos no negativos, y un nodo de inicio S y un nodo R, podría hacer lo siguiente:

• ¿Eliminar el nodo R y actualizar el gráfico de todos modos, de modo que todas las rutas más cortas desde S a otros valores N-2 sean iguales?

Por ejemplo, digamos que se nos da el Gráfico G1 de N = 5 y el Nodo de inicio = 1. Digamos que los valores de ruta más cortos son los siguientes:

• SP (1, 2) = 3, SP (1, 3) = 5, SP (1, 4) = 9, SP (1, 5) = 12
• Ahora, eliminemos R = 3 y actualice el gráfico de todos modos y tengamos G2
• Los nuevos caminos más cortos son:
• SP (1, 2) = 3, SP (1, 4) = 9, SP (1, 5) = 12 -> MISMO

Dijkstra = Loop N-1 veces
– Encuentra el Nodo R con el menor costo posible
– Eliminar R y actualizar el gráfico

El algoritmo de Dijkstra esencialmente utiliza la primera búsqueda de amplitud con un enfoque codicioso para llegar a la distancia más corta entre dos vértices dados.
Deje que el nodo en el que estamos comenzando se llame el nodo inicial. Definimos la distancia del nodo ‘Y’ como la distancia desde el nodo inicial / nodo inicial hasta el nodo ‘Y’. El algoritmo de Dijkstra asignará algunos valores de distancia iniciales e intentará mejorarlos paso a paso.

1. Asigne a cada nodo un valor de distancia tentativo: ajústelo a cero para nuestro nodo inicial y al infinito para todos los demás nodos.
Este paso significa que al comienzo del algoritmo, el nodo inicial está a una distancia 0 de sí mismo y otros nodos son inalcanzables.

2. Establezca el nodo inicial como actual. Marque todos los demás nodos sin visitar. Cree un conjunto de todos los nodos no visitados llamado conjunto no visitado.

3. Para el nodo actual, considere todos sus vecinos no visitados y calcule sus distancias tentativas. Compare la distancia tentativa recién calculada con el valor asignado actual y asigne el más pequeño. Por ejemplo, si el nodo actual A está marcado con una distancia de 6, y el borde que lo conecta con un vecino B tiene una longitud 2, entonces la distancia a B (a través de A) será 6 + 2 = 8. Si B era previamente marcado con una distancia mayor que 8 y luego cámbielo a 8. De lo contrario, mantenga el valor actual.

4. Cuando hayamos terminado de considerar a todos los vecinos del nodo actual, marque el nodo actual como visitado y elimínelo del conjunto no visitado. Un nodo visitado nunca se volverá a comprobar.

5. Si el nodo de destino se ha marcado como visitado (cuando se planifica una ruta entre dos nodos específicos) o si la distancia tentativa más pequeña entre los nodos en el conjunto no visitado es infinito (cuando se planifica un recorrido completo; ocurre cuando no hay conexión entre el nodo inicial y nodos restantes no visitados), luego deténgase. El algoritmo ha terminado.

6. De lo contrario, seleccione el nodo no visitado que está marcado con la distancia tentativa más pequeña, configúrelo como el nuevo “nodo actual” y vuelva al paso 3.

Aquí hay un video que ilustra este algoritmo con un ejemplo.

(Editar: tenga en cuenta que esto originalmente respondió una pregunta ligeramente diferente. Esta respuesta no es una prueba).

Probablemente haga el algoritmo de Dijksta inconscientemente de manera regular, aunque su modelo de costos es más complejo, por lo que no es tan obvio.

Tal vez tenga que hacer varios mandados hoy. Sabes que debes detenerte en la cafetería, la oficina de correos, la tienda de comestibles y el farmacéutico. Todos estos se encuentran en la ciudad en la que vive, por lo que solo camina entre ellos y optimiza el tiempo, lo que, suponiendo intersecciones simples, también se optimiza para la distancia a pie.

En su cabeza tiene un mapa mental bastante preciso de cuán separados están estos lugares, por lo que se le ocurre una ruta que primero va a la más cercana, luego desde allí va a la más cercana y repite para su tercer y cuarta parada.

Ahora en el mundo real, su modelo de costos es más complejo. Sabes que un camino, por ejemplo, te lleva a la tienda de mascotas donde están todos los lindos cachorros, por lo que mentalmente te quitas un poco de dinero porque te gusta verlos, así que da esa preferencia. El camino más corto entre dos de los otros lugares implica una carretera concurrida sin sendero para caminar, por lo que tiene un alto costo para evitar eso. Realmente no desea llevar sus compras a todos los demás lugares, por lo que decide poner eso al final.

Es por eso que intuitivamente sabe que aunque el camino directo al farmacéutico es el más corto desde su hogar, involucra esa carretera concurrida, por lo que tiene más sentido ir primero a la oficina de correos y luego tomar el callejón desde allí hasta el farmacéutico. Es por eso que, al conducir, a veces elegirá una forma que no implique giros en el tráfico ocupado, porque estos presentan un mayor costo mental para usted.

Sin embargo, en esencia, es muy natural pensar que cada día nos movemos en términos de llegar primero al lugar más cercano / más rápido, y luego llegar al siguiente lugar de manera similar. Es bastante raro para nosotros construir un modelo mental que analice con precisión cada punto de nuestros viajes, sino que simplemente piense en llegar al siguiente desde el que estamos.

Esto, por supuesto, no es realmente todo lo que implica el algoritmo. La ilustración común de esto implica hormigas idealizadas que no retroceden, con la observación de que cuando salen de la colmena primero llegarán a varios puntos por los senderos más simples para llegar allí. El Algoritmo de Dijkstra simplemente dice que el costo más bajo para llegar a un lugar determinado desde cualquier lugar debe ser necesariamente el costo más bajo de la (s) ruta (s) para llegar allí, sin importar por qué otros puntos pasaron, y se presenta una forma eficiente de asegúrese de analizar cada costo sin repeticiones innecesarias.

El algoritmo de Dijkastra descubre la ruta más corta en un gráfico ponderado. Básicamente comienza desde el nodo fuente y visita todos los nodos adyacentes no visitados que tienen un peso mínimo. El resultado de este algoritmo es que el algoritmo es un árbol de expansión mínimo que tiene una distancia mínima a todo el nodo desde el nodo fuente.

Ahora, para entenderlo mejor, tomemos un ejemplo de red telefónica. Queremos usar una red que tenga el ancho de banda máximo.
El ancho de banda de una línea de transmisión es la frecuencia más alta que puede soportar la línea. En este gráfico, los vértices representan la estación de conmutación, los bordes representan la línea de transmisión y el peso de los bordes representa el ancho de banda.

considere estos pesos como ancho de banda

Consideremos un conjunto de distancias de vértices
(0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞) como estamos al principio en 0

ahora considerándolo vértices adyacentes 1 y 7 y su valor de distancia se actualiza como 4 y 8.

ahora se convierte en (0, 4, ∞, ∞, ∞, ∞, ∞, 7, ∞) 4 es el peso mínimo, por lo que se elegirá el vértice adyacente a 1

Como 12 es menor que ∞, entonces su distancia desde 0 será 12
vértice visitado (0,1)

ahora de nuevo recogiendo el vértice con el menor peso entre el vértice no visitado (indicado en rojo), es decir, 7 y sus vértices adyacentes que no han sido visitados

Repitiendo los pasos anteriores obtenemos este árbol de expansión mínima o el árbol de ruta más corta.

Libera una gran pila de hormigas que corren a la misma velocidad en el nodo de origen. Ahora vea en qué orden visitan los otros nodos del gráfico.

A medida que las hormigas gotean hacia afuera, te darás cuenta de que primero alcanzan el nodo más cercano, luego el segundo nodo más cercano, etc.

Si está familiarizado con la búsqueda de amplitud primero, también puede imaginar dividir cada borde de longitud L en L bordes de longitud 1, y luego ejecutar la búsqueda de amplitud primero. Por supuesto, esto no funciona en la práctica, pero da una idea de cómo funciona el algoritmo.

Aquí se pueden encontrar pruebas más rigurosas: ¿Cuál es la prueba intuitiva más simple del algoritmo de ruta más corta de Dijkstra?

La respuesta de Anders Kaseorg es exhaustiva, pero no creo que sea particularmente simple o intuitiva. El algoritmo de Dijkstra probablemente encuentra los caminos más cortos porque sigue el principio de programación dinámica; la ruta más corta a un nuevo nodo es la ruta más corta a su predecesor más el costo del borde desde el predecesor hasta el nuevo nodo. Si alguna vez agrega un nodo ‘nuevo’ que ya tiene una ruta, actualícelo solo si el costo es menor. Combine esto con un enfoque que evalúe todas las formas posibles de llegar a un nuevo nodo en cada iteración del algoritmo, y garantiza que después de cada iteración las rutas y los costos para los nodos recién agregados son mínimos.

Como una analogía simple, es como iterar sobre una matriz de enteros y registrar el valor mínimo. minVal = min(newVal, minVal) algo como minVal = min(newVal, minVal) . Siéntase libre de pasar horas ‘demostrando’ que esto produce el valor mínimo, o simplemente acepte que, como lo hace en cada iteración, por lo tanto, debe hacerlo en su totalidad.

Vas a casa desde tu oficina. Hay muchas rutas que puedes tomar para ir a casa. Pero hoy es el cumpleaños de tu esposa y no quieres llegar tarde. Por lo tanto, desea encontrar una forma óptima posible de llegar lo más rápido posible. Pero tienes una ventaja. Tus amigos viven en cada una de las rutas posibles para ir a casa.

Su oficina está en el nodo 1 y su hogar está en el nodo 5.
1) Usted sabe que la ruta directa entre la oficina y la casa es demasiado pequeña y tiene mucho tráfico, por lo que tomará al menos 100 minutos. Entonces llamas a tus amigos en ruta indirecta que son hacia 2 y 4.
2) La ruta hacia 2 es una autopista, pero tu amigo dice que tomará al menos 50 minutos ir de 2 a 3, por lo que debes buscar otras opciones.
3) Llama a su amigo en la ruta 4, quien le dice que casi no hay tráfico hasta la intersección 3. Pero hay mucho tráfico de 4 a 5, lo que tomará al menos 60 minutos.
4) Sabes que hay una autopista de 3 a 5 y no te llevará mucho tiempo volver a casa.

Entonces tomas la ruta 1 – 4- 3 – 5. Y puedes llegar en 1 hora para celebrar el cumpleaños de tu esposa y ella está feliz.

No creo que sea más intuitivo, pero creo que la siguiente explicación ofrece una intuición diferente a las respuestas actuales, y así es como pienso sobre el problema.

El algoritmo de Dijkstra funciona marcando un vértice a la vez a medida que descubre un camino más corto hacia ese vértice. Inicialmente, marcamos solo el vértice s, ya que sabemos su camino más corto (trivial) de s. Dijkstra se basa en una idea clave de la programación dinámica. Considere el camino más corto desde s hasta algún vértice w. Atraviesa una secuencia de vértices, con un vértice final v que luego se conecta a w para finalizar el camino más corto a w. La observación clave es que la ruta hasta v debe ser la ruta más corta hacia v. Porque si no fuera así, podríamos reemplazar esa ruta hacia v con una ruta más corta, lo que también acortaría la ruta hacia w, lo que contradeciría el afirman que tenemos un camino más corto hacia w.

Supongamos que ha marcado (encontrado las rutas más cortas a) un conjunto de vértices M. Voy a definir un tipo especial de ruta llamada ruta de salida: es una ruta más corta a algún vértice v en M (que hemos ya encontrado) seguido de atravesar un solo borde de v a algún vértice w no en M.

¿Por qué son especiales las rutas de salida? Bueno, supongamos que w es el vértice más cercano a s que no está en M. Como acabamos de argumentar, el camino más corto hacia w pasa por una secuencia de vértices con algún vértice v justo antes de M. Pero eso significa que v está más cerca de s que w es, lo que significa que v está marcado (porque elegimos w como el vértice más cercano a s que no está marcado). ¡Y eso significa que el camino más corto hacia w es de hecho el camino de salida hacia w a través de v!

Esto nos dice cómo hacer crecer nuestro conjunto de vértices marcados. Simplemente encuentre la ruta de salida más corta desde M. Según nuestro argumento en el párrafo anterior, esta es la ruta más corta para algunos w. Entonces podemos marcar w y agregarlo a nuestro conjunto M. Ahora repetimos todo el proceso para encontrar otro vértice, y así sucesivamente hasta que hayamos marcado todos los vértices, en cuyo punto tenemos todos los caminos más cortos.

Dijkstra descubrió una forma particularmente eficiente de implementar el algoritmo abstracto que acabo de describir. A saber, define la etiqueta para cada vértice no marcado w como la longitud de la ruta de salida más corta a w. Como acabo de explicar, la etiqueta más pequeña corresponde a una ruta más corta real; podemos agregar el vértice no marcado w de la etiqueta más pequeña a M.

Pero cuando agregamos ese vértice w a M, hemos cambiado M y eso significa que nuestras etiquetas podrían estar equivocadas. En particular, al agregar w a M hemos hecho posibles nuevas rutas de salida. Entonces, para arreglar las cosas, solo miramos todas las rutas de salida que salen de M a través de w. Si el camino más corto hacia w, seguido de atravesar un solo borde de w a x, nos da una distancia menor que la etiqueta actual de x, entonces actualizamos (reducimos) la etiqueta de x. Esto mantiene la invariante (otra idea inventada por Dijktra, posiblemente más importante que su algoritmo de rutas más cortas) de que las etiquetas son correctas.

Confiando en esta invariante, podemos implementar el algoritmo. Almacenamos las etiquetas en una cola prioritaria. Esto nos permite actualizar las etiquetas cuando lo necesitamos, y también nos permite extraer la etiqueta mínima cuando la necesitamos. Siempre que extraemos el vértice mínimo de la etiqueta w, conocemos su ruta más corta, por lo que podemos agregarlo a M. Luego, actualizamos todas las rutas de salida desde w.

El algoritmo de Dijkstra funciona porque:

1. El vértice con la distancia más corta desde cualquier vértice (o un conjunto dado de vértices) debe ser un vértice, que está conectado al vértice (o conjunto de vértices) por un borde directo .
2. El algoritmo garantiza que los vértices se agregan al conjunto de vértices actual en orden de aumentar la longitud de la ruta más corta desde el vértice de origen,

Prueba para el punto 1 : si el vértice con la distancia más corta (por ejemplo, V) está conectado por un camino con múltiples bordes al conjunto de vértices actual (falso, pero suponga esto por razones de prueba), habrá un vértice [matemático] V_1 [/ math] en la ruta que conecta el conjunto de vértices a V, que tendrá una distancia más corta que V. Por lo tanto, V nunca puede ser el vértice con la distancia más corta desde el conjunto de vértices.

Prueba para el punto 2:

Usaré la inducción para probar este punto:

Sea [math] A_i [/ ​​math] el vértice con [math] i ^ {th} [/ math] la distancia más corta desde el vértice fuente. Obviamente, [matemáticas] A_1 [/ matemáticas] = S (Fuente)

Base:

Asuma el caso al inicio del algoritmo cuando solo el vértice fuente S está presente en el conjunto de vértices actual. [matemática] A_2 [/ matemática] es ese vértice que está conectado al borde más corto desde S. [matemática] A_2 [/ matemática] no puede tener una ruta más corta desde el vértice fuente ya que todos los demás bordes son más largos.

Prueba por inducción:

Supongamos que ya agregamos los N vértices con la distancia más corta desde la fuente al conjunto de vértices. Vértice [matemática] A_ {N + 1} [/ matemática] debe tener un borde directo de al menos 1 vértice en el conjunto de vértices actual (debido al punto 1). Al actualizar distancias basadas en el descubrimiento de N nodos, el nodo que no está en el conjunto de vértices actual y tiene la menor distancia desde el nodo fuente debe ser vértice [matemática] A_ {N + 1} [/ matemática] ya que tiene la ruta más corta desde la fuente entre nodos que no están en el conjunto de vértices. Por lo tanto, probamos el segundo punto.

El algoritmo de Dijkstra nos permite encontrar las rutas más cortas en un gráfico desde un nodo dado, como este:

Los bordes podrían representar caminos entre intersecciones, por ejemplo, y las etiquetas podrían representar la distancia del camino, la cantidad de tiempo que pasa en el camino, el costo del combustible en el camino, etc. Digamos que es el momento. Queremos encontrar la cantidad mínima de tiempo que nos llevará conducir desde A hasta cualquiera de los otros nodos.

Para hacer esto, construimos iterativamente un conjunto de nodos para los que conocemos el camino más corto. Me saltearé los primeros pasos y diré que conocemos los caminos más cortos de A a B y a F.

Aquí, tenemos una “burbuja” de A, B y F. Pero siendo los exploradores que somos, queremos profundizar fuera de nuestra zona de confort. ¿Cuál es el camino más corto fuera de nuestra burbuja, desde A? Aquí están todos los bordes que salen de nuestra burbuja, marcados en rojo:

Entonces, ¿cuál es el camino más corto fuera de nuestra burbuja? Podríamos ir A -> B -> C, que lleva tiempo 5. Podríamos ir A -> D, que lleva tiempo 3. Podríamos tomar A -> F -> D, que lleva tiempo 2. Finalmente, podríamos tomar tiempo A -> F -> E, que lleva tiempo 4.

El más corto de ellos es A -> D, lo que lleva tiempo 3. Pero entonces este debe ser el camino más corto hacia D, ya que es el camino más corto fuera de la burbuja, y cualquier camino hacia D tiene que salir de la burbuja en algún momento ! Entonces podemos agregar D a nuestro conjunto “conocido”.

Ahora podemos continuar. ¿Cuál es el camino más corto fuera de nuestra nueva burbuja extendida? Un vistazo rápido muestra que se trata de A-> D-> C o A-> D-> E, cada uno con un costo 4. Así que ahora sabemos los caminos más cortos hacia C y E.

Whee! Ahora sabemos cómo llegar a todas partes en el menor tiempo, desde el nodo A.

Así es como Dijkstra funciona conceptualmente, y la explicación anterior es bastante similar a una prueba de corrección. Tenga en cuenta que hay algunos detalles de implementación para implementar esto de manera eficiente: realizar un seguimiento de la distancia mínima conocida a cada nodo, usar colas de prioridad para seleccionar nodos rápidamente, y así sucesivamente, pero no voy a entrar en eso aquí.

En términos muy simples, el algoritmo de Dijkstra resuelve gráficamente el problema del camino más corto. Para un principiante, diría que considera que tiene 5 lugares en una ciudad, puede ir de un lugar a otro a través de un camino que tendrá cierta distancia. No es necesario que todos los lugares estén directamente conectados entre sí, pero si forman parte del gráfico, estarán conectados indirectamente y pueden tener más de una ruta. Ahora dado el origen y el destino, el algoritmo de Dijkstra le dará la ruta más corta y su distancia. Dijkstra encuentra el camino más corto encontrando el nodo con la distancia mínima (desde la fuente actual) y visitando a todos los vecinos no visitados de este nodo de distancia mínima. El algoritmo procede de esta manera para encontrar un árbol de expansión mínimo que denota la distancia mínima a todos los demás nodos desde el nodo de origen.

Depende del dominio en el que estemos aplicando el algoritmo de Dijkstra.

En un gráfico de distancia sería difícil. Pero no tiene que ser un gráfico de distancia.

Digamos, una niña está vistiendo su juguete. Se puede usar ropa diferente. Algunos tienen restricciones de orden. Algunos no encajan.

La niña tiene una imagen final en mente.

Para este problema, el tiempo que pasa poniéndose y quitándose cierta prenda es el costo. Este costo es algo que nos gustaría minimizar.

Primero, descubrimos que quitarse la ropa solo desperdicia tiempo. Entonces, elimínelos si buscamos la solución más rápida.

Entonces, algunas órdenes tienen más sentido que las otras. Ven con algunos ejemplos. La camiseta puede ser más fácil de poner antes de los jeans o viceversa. Nunca tuve la oportunidad de jugar con muñecas.

Después de esto llegamos a la idea de subtrayectos óptimos. Básicamente, si en la solución más rápida debemos pasar por cierta etapa (“bragas, jeans, camiseta, nada más”), entonces solo importa qué tan rápido podemos llegar a esta etapa, no el orden en sí.

Suena duro … pero puede funcionar al final.

Si está convencido de que BFS en un gráfico no ponderado * es * un algoritmo de ruta más corta, puede reescribir un gráfico ponderado como un gráfico no ponderado con un borde con peso k desglosado en k bordes con peso 1.

La solución es pseudo-polinomial, pero es correcta.

Aquí se ha respondido, y también brillantemente, ¿cuál es la prueba intuitiva más simple del algoritmo de ruta más corta de Dijkstra?

El algoritmo de Dijkstra proporciona la distancia más corta entre un vértice fuente y un vértice objetivo en un gráfico ponderado. Básicamente, el algoritmo de Dijkstra pertenece a la programación dinámica y al paradigma codicioso de los algoritmos.

Comienza desde el borde de peso mínimo desde el vértice de origen y descubre nuevos bordes que se originan desde el vértice final del borde que tiene un peso mínimo en cada paso. Relaja la distancia desde el vértice de origen hasta el vértice final actual si es necesario.

Digamos que está tratando de conducir desde Nueva York a Los Ángeles, pero debe usar solo las carreteras. Ignorando los costos de la gasolina, queremos minimizar el costo total del peaje del viaje. Entonces, digamos que comenzamos yendo desde Nueva York a, digamos, Pittsburgh, luego a Cleveland, Ohio, y cuesta $ 12. ¡Pero espera! Si pasas por Virginia y luego a Cleveland, cuesta solo $ 10. Por lo tanto, suponemos que cuesta $ 10 llegar a Cleveland. Si hay una mejor solución, la reemplazamos hasta obtener el costo más bajo en cada punto. De esta manera, hemos logrado reducir nuestro costo total para llegar a Cleveland.

Ahora, continúe este proceso a través de cada paso del camino hasta llegar a la última ciudad, el destino. Ahora tiene el costo de peaje más bajo y, con suerte, un mapa que indica la ruta más barata para almacenar para referencia futura.

En términos de CS, el algoritmo de Dijkstra encuentra la ruta más corta (peso más bajo) en un conjunto de rutas dadas una entrada y una salida y un peso en cada paso.

Imagine que cada borde en el gráfico consiste en árboles. Entonces el algoritmo Dijkstra es solo un incendio forestal iniciado en un punto.

Lo pienso así:
Si estoy parado en el nodo de origen en el territorio conquistado (las distancias más cortas a los nodos de las cuales ya se han calculado), entonces para salir de este territorio y explorar un poco más del mundo, tomaría el cruce de puente más pequeño el territorio teniendo en cuenta la distancia que debería cubrirse para llegar a ese puente también. Puedo ver los números que he marcado en los nodos que unen mi territorio con el mundo exterior. Estos números me dicen cuán lejos está un puente en particular de mí ahora. Es un problema fácil después de eso. Miro las longitudes del puente y los números y comienzo mi viaje 🙂