READS, EJERCICIO Paso a Paso
Encuentre la ruta más corta de la siguiente red. Los números representan las distancias
correspondientes reales entre los nodos.
SOLUCIÓN:
Para resolver problemas de ruta más corta se debe proceder con el criterio del Algoritmo de
Dijktra. Esto es debemos partir del origen (O) y debemos llegar al Destino (T) y lo debemos hacer por
el camino o ruta más corta. Es decir tenemos que optimizar, minimizando costos de envío del nodo
Origen al Nodo destino.
Veamos que la red tenemos tiene 11 nodos:
Al salir del Nodo O se puede llegar a los Nodos A, B y C. pero fíjense que se puede hacer a
distintos costos 4, 3 y 6. Respectivamente. Lo cual se muestra con cuadrados rojos sobre los nodos
alcanzados o conocidos. OA=4, OB=3, OC=6
Ahora vamos a llegar al Nodo D; pueden ver que los nodos conocidos más cercanos son A y C.
por lo tanto se puede llegar a D desde A con 4+3=7; pero se puede llegar a D dese C con 6+2=8, como
nos interesa el camino más corto elegimos AD para un costo de 7.
Ahora vamos a llegar a E; pueden ver que los nodos conocidos más cercanos son B y C. por
tanto se puede llegar a E desde B con 3+6= 9; pero se puede llegar a E desde C con 6+5=11, como nos
interesa el camino más corto elegimos BE con un costo de 9.
Ahora vamos a llegar a F; puede verse que los nodos conocidos más cercanos son C, D y E, por
tanto se puede llegar a F desde C con 6 + 2= 8; pero se puede llegar a F desde D con 7+2=9; pero
también se puede llegar a F desde E con 9+1=10; puede verse que el más corto de los tres es 8 por lo
que elegimos CF.
Ahora podemos alcanzar G desde los nodos conocidos más cercanos D y F. por tanto se puede
llegar a G desde D con 7+4=11; pero se puede llegar a G desde F con 8+2=10; puede verse que es
menos costoso llegar desde F por lo que elegimos FD.
Ahora podemos alcanzar H desde los nodos conocidos más cercanos E, F y G. Por tanto se
puede llegar H desde E con 9+2= 11; pero se puede llegar a H desde F con 8+5=13; pero se puede llegar
a H desde G con 10+2=12; puede verse que el menos costoso es de EH con 11.
Ahora podemos alcanzar I desde los nodos conocidos más cercanos E y H. Por lo tanto se
puede llegar a I desde E con 9+5=14; pero puedo llegar I desde H con 11+3=14; vemos que los costos
son iguales desde E o desde H, por lo que hay dos opciones posibles. HI y EI
Ahora podemos alcanzar el nodo destino T desde los nodos conocidos más cercanos G, H e I.
Por tanto puedo alcanzar T desde G con 10+7=17; pero puedo alcanzar T desde H con 11+8=19 o
puede alcanzar T desde I con 14+4=18, puede verse que de los tres el menos costoso es 17 desde GT
Resultando la ruta óptima: OC-CF-FG-GT o lo que es lo mismo O-C-F-G-T = 17
En Resumen:
Una ciudad tiene cinco subdivisiones. El alcalde desea instalar líneas telefónicas, para asegurar
la comunicación entre todas las subdivisiones. En la figura se dan las distancias entre las subdivisiones.
¿Cuál es la longitud mínima necesaria de la línea telefónica?
SOLUCIÓN:
Las cinco subdivisiones son los nodos 1, 2, 3, 4, 5 encerrados en círculo. Las distancias entre las
subdivisiones están dadas en kilómetros, puede ver que el nodo uno pude conectar a la subdivisión 2, 3
y 5.
Este problema es del tipo de árbol de expansión mínima; para su solución elegimos la conexión
más pequeña o más corta entre dos subdivisiones de la ciudad. Puede ver que hay dos posibles:
Conectar el Nodo 3 con el Nodo 1 o el Nodo 3 con el Nodo 5 por resulta más económico, menos
cableado y menos postes. Pues conectamos:
El Nodo 3 con el Nodo 1. Con una distancia de 3 Km
El Nodo 3 con el Nodo 5. Con una distancia de 3 Km.
El Nodo 3 con el Nodo 4. Con una distancia de 4 Km.
El Nodo 1 con el Nodo 2. Con una distancia de 5Km.
Para un total de 15 Km de cableado y tendido de poste y está sería la decisión óptima.
Es bueno que sepa que la última conexión pudo hacerse del Nodo 3 al nodo 3 por que también
tiene 5 Km.
Las instalaciones se deberán hacer en los arcos pintados de rojo.
