Ejercicios
Mtodo de la ruta ms corta
Ejercicios resueltos:
1. Determinar la ruta ms corta a seguir para llegar a F y los kilmetros
recorridos, si se parte desde A. Ver red con distancias en kilmetros.
20
10
5
3
8
E
15
4
3
15
D4
15
a. Identificamos el inicio y lo rotulamos:
A [0, -].
b. Rotular los nodos siguientes, que dependan nicamente del inicial.
En este caso solo D porque a D solo se puede llegar desde A: D
[15, A].
c. Rotular nodos que dependan de nodos ya rotulados, analizndolos
en orden:
B depende de A y C, por tanto habr que rotular primero C.
C depende de A y D, ambos rotulados. Rotulamos eligiendo la
ruta ms corta entre ambas:
o Desde A hasta C se recorren 8 Km.
o Desde D, habiendo salido de A, se recorren 19 Km.
Elegimos A y procedemos a rotular: C [8, A].
Ya es posible rotular B que depende de A y C:
o Desde A hasta B se recorren 10 Km.
o Desde C, saliendo de A, se recorren 11 Km.
Elegimos A, por tanto: B [10, A].
Es turno de rotular E que depende de B y C:
o Desde B, saliendo de A, se recorren 30 Km.
o Desde C, saliendo de A, se recorren 23 Km.
Elegimos C: E [23, C].
Rotular F que depende de C y D:
o Desde C, saliendo de A, se recorren 12 Km.
o Desde D, saliendo de A, se recorren 30 Km.
Elegimos C: F [12, C].
d. Procedemos a rotular el nodo de llegada, el G, una vez rotulados
todos los nodos previos:
G depende de E y F:
o Desde E se recorreran 28 Km. saliendo de A y pasando por
C.
o Desde F, 15 Km. saliendo de A y pasando por C.
Elegimos F: G [15, F].
e. A partir del nodo de llegada, determinamos la ruta a seguir: Se llega
a G desde F, habiendo pasado por C y salido de A, La ruta a seguir
es A-C-F-G y se recorrern 15 Km. (Ver flechas rojas para entender la
seleccin).
2. El rea de logstica necesita encontrar la ruta ms corta en kilmetros
desde la planta (nodo O) hasta el almacn central (nodo T) a travs del
sistema de caminos que se presenta en la figura siguiente:
a. Identificamos el inicio y lo rotulamos:
O [0, -].
b. Rotular los nodos siguientes, que dependan nicamente del inicial.
En este caso A y C porque a ambos solo se puede llegar desde
O:
o A [2, O].
o C [4, O].
c. Rotular nodos que dependan de nodos ya rotulados, analizndolos
en orden:
B depende de O, A y C que ya fueron rotulados, por tanto:
o Desde O hasta B, directamente se recorreran 5 Km.
o Desde A, habiendo salido de O, se recorren 4 Km.
o Desde C, habiendo salido de O, se recorren 5 Km.
Para llegar a B conviene pasar primero por A ya que la ruta es
ms corta. Entonces: B [4, A].
D depende de A y B, ambos rotulados. Rotulamos eligiendo la
ruta ms corta entre ambas:
o Desde A hasta D, saliendo de O, se recorren 9 Km.
o Desde B, habiendo salido de O y pasado por A, se recorren 8
Km.
Elegimos B y procedemos a rotular: D [8, B].
E depende de B y C, ambos rotulados. Rotulamos eligiendo la
ruta ms corta entre ambas:
o Desde B, pasando por y saliendo de O, se recorren 7 Km.
o Desde C, habiendo salido de O, se recorren 8 Km.
Elegimos B y procedemos a rotular: E [7, B].
d. Procedemos a rotular el nodo de llegada, el T, una vez rotulados
todos los nodos previos:
T depende de D y E:
o Desde E se recorreran 14 Km. saliendo de O y pasando por A
y B.
o Desde D, 13 Km. saliendo de O y pasando por A y B.
Elegimos D: T [13, D].
e. A partir del nodo de llegada, determinamos la ruta a seguir: Se llega
a T desde D, habiendo pasado por B y A y salido de O, La ruta a
seguir es O-A-B-D-T y se recorrern 13 Km. (Ver flechas rojas para
entender la seleccin).
Ejercicios propuestos
1. Determine la ruta ms corta aplicado el mtodo respectivo. Indique
nodos dentro de la ruta y distancia total en kilmetros. Considere como
punto de partida el nodo A y como de llegada al nodo H.
3
4
3
2
D
5
7
12
2. Una persona tiene que trasladarse a diario del pueblo A al pueblo G est
estudiando cul es el trayecto ms corto usando un mapa de carreteras.
Las distancias en kilmetros estn representadas en la siguiente matriz:
A
B
C
D
E
F
G
A
-
B
6
-
C
4
D
1
3
-
E
4
1
3
4
4
9
-
Grafique la red correspondiente, a partir de las distancias presentadas
en la matriz y luego aplique el mtodo de la ruta ms corta indicando la
ruta a seguir y la distancia total recorrida en kilmetros.
Nota:
Los datos de la matriz se leen de la siguiente manera: De un nodo X i a
un nodo Yj, hay Nij kilmetros. Xi corresponde a cualquiera de los valores
de la columna izquierda (A, B, C, D, E, F o G), Y j corresponde a
cualquiera de los valores de la fila superior (A, B, C, D, E, F o G) y N ij a la
distancia correspondiente entre Xi e Yj.
3. Determinar la ruta ms corta a partir del siguiente grafo.
