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.
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:
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?
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.
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.
(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).
(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:
ES 
FR 
EN