Taller 4 - Sistema de distribución

4) A partir de una red de transporte definida (ver figura) determine la ruta óptima para llegar desde el punto origen O hasta el punto destino T considerando el Algoritmo de Dijkstra. Para determinar los costos en función de la distancia de cada uno de los nodos considere las coordenadas de cada punto dadas.

Figura:

Tabla:

NODO	X	Y
O	80	150
A	210	200
B	150	80
C	240	120
D	280	180
E	260	60
F	300	100
T	360	130

Sol:

Teniendo en cuenta las coordenadas en el plano X – Y se utiliza el teorema de Pitágoras para determinar las distancias entre los puntos asumiendo de que se puede avanzar en línea recta desde un punto a otro.

Se tiene que el teorema de Pitágoras es: c^2=a^2 + b^2 , donde a será las coordenadas en X y b será las coordenadas en Y por lo tanto c será las distancias en líneas rectas de un punto a otro.

1.    De este modo se tomarán las distancias de X y Y entre nodos y se evaluarán la distancia resultante.

2.   

Luego se tomarán las distancias resultantes y se aplicará el teorema de Pitágoras para determinar la distancia en línea recta.

Distancia de O hasta el nodo A:

O = 80X;150Y       A= 210X;200Y

 Entonces:

X_((oa))= X_a-X_o=210-80=130  (Distancia en eje X desde O hasta A)

Y_((oa))= Y_a-Y_o=200-150=50 (Distancia en eje Y desde O hasta A)

 

Distancia desde O hasta A
	Coord. O		Coord. A		Dist. O – A		Distancia
NODO	X	Y	X	Y	X	Y	c
O - A	80	150	210	200	(210-80) =130	(200-150) =50	c^2= 130^2+ 50^2=19400 c=139.283

 NODOS             Cálculos                                                             Distancia

O – A c= √(〖(210-80)〗^2+ 〖(200-150)〗^2 )  =139.283     139.28

O – B c= √(〖(150-80)〗^2+ 〖(80-150)〗^2 )  =98.994             98.99

B – E c= √(〖(260-150)〗^2+ 〖(60-80)〗^2 )  =111.803             111.80

A – C c= √(〖(240-210)〗^2+ 〖(120-200)〗^2 )  =85.440     84.44

C – D c= √(〖(280-240)〗^2+ 〖(180-120)〗^2 )  =72.111     72.11

C – F c= √(〖(300-240)〗^2+ 〖(100-120)〗^2 )  =63.245     63.24

E – T c= √(〖(360-260)〗^2+ 〖(130-60)〗^2 )  =122.065     122.06

D – T c= √(〖(360-280)〗^2+ 〖(130-180)〗^2 )  =94.339     99.34

F – T c= √(〖(360-300)〗^2+ 〖(130-100)〗^2 )  =67.082     67.08

Diagrama Con distancias:

 

Diagrama Solución con Algoritmo de Dijkstra:

De determina que la ruta optima es: