Problema del camino más corto

Esta página presenta varios ejercicios corregidos sobre el problema de camino más corto. Los ejercicios se enfocan en el camino más corto hacia una fuente y el camino más corto desde múltiples fuentes.

camino más corto camino más corto ejercicios corregidos dijkstra bellman ford-bellman

Ejercicio 1

La aerolínea Europa sirve a varias ciudades europeas. La siguiente tabla muestra los tiempos de vuelo entre estas ciudades.
• ¿Cómo determinar la ruta más rápida entre dos ciudades?
• ¿Cómo modificar el método anterior para tener en cuenta la duración de las escalas en las distintas ciudades?

 

PARA

B

VS

D

mi

PARA

 

1h30

2h00

 

2h15

B

1h40

   

3h00

VS

2h20

  

2h55

 

D

  

3h20

 

1h05

mi

2h25

3h10

1h10

  

Solución

Solo dibuja el grafico, cuyos vértices son las ciudades y los arcos las rutas de la empresa, valorándose en cada arco la longitud del vuelo correspondiente. A algoritmo la ruta más corta resuelve el problema.
Para tener en cuenta la duración de las escalas, son posibles dos métodos: Editar el algoritmo anterior, incluyendo el costo de la escala en los arcos O: se duplica cada vértice; un arco entre ellos es la escala de la ciudad correspondiente.

camino más corto camino más corto ejercicios corregidos dijkstra bellman ford-bellman

Ejercicio 2

Queremos construir una nueva fábrica en la siguiente red, los nodos son lugares y los enlaces representan los costos para enviar energía de un lugar a otro:

camino más corto camino más corto ejercicios corregidos dijkstra bellman ford-bellman

Basado en el algoritmo de Dijkstra, proponga un método para encontrar el mejor lugar para construir la fábrica y luego resuelva el problema con su método. Resolver el problema con el algoritmo de Floyd-Warshall.

Solución

Necesitamos calcular Dijkstra para cada nodo (en el nodo de origen). Una vez que se crea el árbol de rutas, agregue el costo de todas las rutas desde cualquier nodo al nodo de origen (agregue la última matriz de rutas más cortas). El mejor lugar es el peso total mínimo de todas las ocurrencias de Dijkstra. Con Floyd-Warshall, la matriz de pseudocierre contiene todos los arreglos, simplemente sume las entradas de cada arreglo y encuentre el mínimo.

Ejercicio 3

Un robot se mueve a través del siguiente entorno. Comienza desde el nodo etiquetado como inicio y debe llegar al nodo etiquetado como final. El entorno es continuo y la escala se proporciona en la figura. Considerando que el robot es un punto, ¿cuál es el camino más corto de principio a fin?

camino más corto camino más corto ejercicios corregidos dijkstra bellman ford-bellman

Solución

Calcular la distancia euclidiana entre nodos. Dibuje el gráfico y aplique el algoritmo de Dijkstra para encontrar la ruta más corta desde el nodo Estrella hasta el nodo Final. Luego dibuja el camino en la figura.

Camino más corto

Comienzo

1

2

3

Fin

En eso

0

inf

inf

inf

inf

Comienzo

raíz cuadrada 5

raíz cuadrada 29

inf

inf

1

raíz cuadrada 29

sqrt 5+ sqrt 26

inf

2

sqrt 5+ sqrt 26

raíz cuadrada 29 + raíz cuadrada 17

3

raíz cuadrada 29 + raíz cuadrada 17

La ruta más corta es Start-2-End.

Ejercicio 4

Considerando la gráfica del ejercicio 1, las aristas se dirigen de izquierda a derecha (o de arriba hacia abajo) y los pesos se reducen en 4. ¿Cómo encontrar un camino mínimo de A a F? Resolver.

Solución

Aplicar botones en este gráfico (Un nodo está bloqueado solo si todos sus predecesores están bloqueados).

camino más corto camino más corto ejercicios corregidos dijkstra bellman ford-bellman

 

PARA

B

VS

D

mi

F

en eso

0

inf

inf

inf

inf

inf

A, 0

-1

1

5

inf

inf

B, -1

-2

-1

2

inf

C, -2

-4

0

inf

D, -4

-6

-6

E, -6

-6

F

Ejercicio 5

(a) Calcule el camino más corto desde s hasta todos los demás vértices utilizando el algoritmo de Dijkstra. Determine el árbol de ruta más corto.

(b) ¿Es único el árbol del camino más corto?

(c) Ahora cambie el peso de la arista (3, 4) a −2. Demuestre que el algoritmo de Dijkstra no funciona en este caso.

camino más corto camino más corto ejercicios corregidos dijkstra bellman ford-bellman

Solución

(a) La solución viene dada por la siguiente imagen. Los números al lado de los vértices son las distancias al vértice inicial y tachar un número significa que ha habido una actualización. Los números en los cuadrados indican las distancias finales (distancias más cortas).

camino más corto camino más corto ejercicios corregidos dijkstra bellman ford-bellman

(b) Ninguno árbol el camino más corto es único. Reemplazando la arista (s, 3) por la arista (1, 2) obtenemos otro árbol de caminos más cortos.

(c) El algoritmo de Dijkstra dará la misma solución que en el inciso (a) aunque el camino (s, 1, 2, 3, 4) (dist 5) tiene una distancia más corta que el camino (s, 1, 4) (dist 6). Esto es lo que sucede: después de visitar los vértices s, 1, 2, el algoritmo buscará el camino más corto a un vértice aún no visitado. Este será el vértice 4 con distancia 6. Después de visitar el vértice 4, el algoritmo no se actualizará en el vértice 4 porque ya ha sido visitado y por esta razón no puede encontrar el camino más corto (distancia 5).

Ejercicio 6

Un hombre tiene que llevar un lobo, una cabra y un repollo a través de un río. Tiene un bote para hacerlo, pero es tan pequeño que solo puede llevar una de las tres cosas con él cada vez. ¿Es posible llevar las tres cosas al otro lado del río de forma segura? Tenga en cuenta que el lobo y la cabra o la cabra y el repollo nunca deben estar en el mismo lado del río sin supervisión humana. Al menos el lobo no es vegetariano y no le gusta comer repollo.

Solución

Construimos un gráfico para este problema donde cada estado legal está representado por un vértice en el gráfico y encontramos el camino más corto en este gráfico. Sea S = {M,W,G, C} donde M,W,G, C son el hombre, el lobo, la cabra y el repollo. 

Un estado para este problema es un par (X, Y) donde {X, Y} es una partición de S. Los elementos de X siempre están en el lado inicial del río y los elementos de Y ya están en el otro lado. Un estado es un estado legal si W,G ∈ X, Y ⇒ M ∈ X, Y y G, C ∈ X, Y ⇒ M ∈ X, Y, no puedes dejar solos el repollo y el lobo o la cabra y el repollo desatendidos . 

Construyamos ahora un grafo G = (V, E) que tenga un vértice para cada estado legal de este problema. Tenemos la arista dirigida (v1, v2) ∈ E si podemos pasar del estado v1 = (X1, Y1) al estado v2 = (X2, Y2) en un solo viaje en bote por el río. Todas las aristas tienen un peso ce = 1. Ahora el problema se puede resolver calculando el camino más corto desde el estado (vértice) s = (S, -) hasta el estado (vértice) t = (-, S). Obtenemos 7 como la solución de ruta más corta.

Ejercicio 7

Considere la siguiente modificación del algoritmo de Dijkstra para trabajar con pesos negativos: w(e) = c. Luego, para todas las aristas f en E establecemos w'(f) := w(f) – c. Entonces G'= (V,E,w') no tiene pesos negativos. ¿Esta versión del algoritmo funciona correctamente en este tipo de gráfico? Demuestra tu afirmación.

Solución

Ahora afirmamos que el algoritmo no funciona bien en G' porque esta modificación no conserva la propiedad del camino más corto, es decir, (-c) es un número positivo, por lo que suma n veces para obtener un camino n. El siguiente contraejemplo lo demuestra:

camino más corto camino más corto ejercicios corregidos dijkstra bellman ford-bellman

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: