Esta página presenta varios ejercicios corregidos sobre problemas del camino más corto. Los ejercicios tratan principalmente sobre el camino más corto para una fuente y el camino más corto de muchas fuentes.

Ejercicio 1

La compañía aérea Europa opera en 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 diferentes ciudades?

 

PARA

B

VS

D

mi

PARA

 

1h30

2h00

 

2h15

B

1h40

 

 

 

3h00

VS

2h20

 

 

2h55

 

D

 

 

3h20

 

1h05

mi

2h25

3h10

1h10

 

 

Simplemente dibuja la gráfica, cuyos vértices son ciudades y arcos las rutas de la empresa, valora cada longitud de arco del vuelo correspondiente. Luego, un algoritmo de 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 en arcos el costo de la escala O: cada vértice se duplica; un arco entre ellos es la escala de la ciudad correspondiente.

Ejercicios corregidos sobre problemas del camino más corto.

Ejercicio 2

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

Ejercicios corregidos sobre problemas del camino más corto.

Residencia en Dijkstra algoritmo, propone un método para encontrar el mejor lugar para construir la planta y luego resuelve el problema con su método. Resuelve el problema con Floyd-Warshall algoritmo.

Tenemos que calcular Dijkstra para cada nodo (en el nodo de origen). Una vez que se crea el árbol de rutas, sume el costo de todas las rutas desde cualquier nodo hasta el nodo de origen (sume 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 pseudo-cierre contiene todas las matrices, simplemente sume las entradas de cada matriz y encuentre el mínimo.

Ejercicio 3

Un robot se mueve en el siguiente entorno. Comienza desde el nodo etiquetado comienzo y necesita llegar al nodo etiquetado fin. El entorno es continuo y la escala se suministra en la figura. Teniendo en cuenta que el robot es un punto, ¿cuál es el camino más corto de principio a fin?

Ejercicios corregidos sobre problemas del camino más corto.

Calcule la distancia euclidiana entre los nodos. Dibuje el gráfico y aplique el algoritmo de Dijsktra para encontrar la ruta más corta desde el nodo Estrella hasta el nodo Fin. 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

El camino más corto es Start-2-End.

Ejercicio 4

Considerando el gráfico del ejercicio 1, los bordes se dirigen de izquierda a derecha (o de arriba a abajo) y los pesos se reducen en 4. ¿Cómo encontrar una ruta mínima de A a F? Resuélvelo.

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

Ejercicios corregidos sobre problemas del camino más corto.

 

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 la ruta más corta desde sa todos los demás vértices utilizando el algoritmo de Dijkstra. Determine el árbol del camino 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. Muestre que el algoritmo de Dijkstra no funciona en este caso.

Ejercicios corregidos sobre problemas del camino más corto.

(a) La solución viene dada por la siguiente imagen. Los números junto a 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 cuadrados indican las distancias finales (distancias más cortas).

Ejercicios corregidos sobre problemas del camino más corto.

(b) Ningún árbol de camino más corto no es único. Sustituyendo el borde (s, 3) con el borde (1, 2) se obtiene otro árbol de ruta más corto.

(c) El algoritmo de Dijkstra dará la misma solución que en el inciso (a) aunque la ruta (s, 1, 2, 3, 4) (dist 5) tiene una distancia más corta que la ruta (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 hacia 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 actualizará el vértice 4 porque ya fue visitado y por esta razón no encuentra el camino más corto (distancia 5).

Ejercicio 6

Un hombre tiene que transportar un lobo, una cabra y un repollo al otro lado de un río. Tiene un bote para hacer esto, 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? Note que el lobo y la cabra o la cabra y el repollo nunca deben estar en el mismo lado del río sin la vigilancia del hombre. Al menos el lobo no es vegetariano y no le gusta comer repollo.

Construimos un gráfico para este problema donde cada estado legal está representado por un vértice en el gráfico y buscamos la ruta más corta en ese gráfico. Entonces, 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 en X todavía están en el lado inicial del río y los elementos en 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 solo el repollo y el lobo o la cabra y el repollo sin vigilancia. Ahora construya una gráfica G = (V, E) que tenga un vértice para cada estado legal de este problema. Tenemos el borde dirigido (v1, v2) ∈ E si podemos pasar del estado v1 = (X1, Y1) al estado v2 = (X2, Y2) con solo un viaje en bote a través del río. Todas las aristas obtienen el peso ce = 1. Ahora el problema se puede resolver calculando el camino más corto desde el estado (vértice) s = (S, 😉 al estado (vértice) t = (;, S). Obtenemos 7 como la solución para el camino más corto.

Ejercicio 7

Considere la siguiente modificación del algoritmo de Dijkstra para trabajar con pesos negativos: Determine el peso más pequeño c en ℤ en el gráfico ponderado G = (V, E, w), es decir, el borde e st w (e) = c. Entonces, para todas las aristas f en E, establezca 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? Demuestre su afirmación.

Ahora afirmamos que DJP no funciona correctamente en G 'porque esta modificación no mantiene la propiedad de la ruta más corta, es decir, (-c) es un número positivo, por lo que se agrega n veces para una n-ruta. El siguiente contraejemplo lo demuestra:

Ejercicios corregidos sobre problemas del camino más corto.