Scribd
Cargar
79 vistas4 páginas

Ruta más corta entre nodos O y T

Este documento describe el proceso de determinar la ruta más corta entre dos nodos (O y T) utilizando el algoritmo de Dijkstra. Se etiquetan los nodos de origen y adyacentes, luego se convierte el nodo temporal con el menor costo a permanente actualizando los costos. Este proceso se repite hasta convertir el nodo destino en permanente, indicando que se encontró la ruta óptima de 13 unidades entre O y T a través de los nodos O-A-B-D-T.

Cargado por

hugo_castrillon_2
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
79 vistas4 páginas

Ruta más corta entre nodos O y T

Este documento describe el proceso de determinar la ruta más corta entre dos nodos (O y T) utilizando el algoritmo de Dijkstra. Se etiquetan los nodos de origen y adyacentes, luego se convierte el nodo temporal con el menor costo a permanente actualizando los costos. Este proceso se repite hasta convertir el nodo destino en permanente, indicando que se encontró la ruta óptima de 13 unidades entre O y T a través de los nodos O-A-B-D-T.

Cargado por

hugo_castrillon_2
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

EJEMPLO No 2 DETERMINAR LA RUTA MS CORTA ENTRE LOS

NODOS O y T

7
A D
5
4
2 2
2
1
O B T
5
3 7
1

4
4
C E
Iteracin 01: procedemos a etiquetar el nodo origen y lo convertimos en permanente, luego
etiquetamos los nodos adyacentes, directamente conectados que sern denominados nodos
temporales.

(2, - )(1 ) 7
A D
5
4
(0, 2
2 2
1
O B (5, - )(1 ) T
5
3 7
1
4
4
4
C E
(4, - )(1 )

Iteracin 02: de alguno de los nodos temporales elegimos aquel que tenga el menor costo total
asociado y lo convertimos en permanente y actualizamos los nodos temporales.

(2, - )(1 ) A
7
D (9, A )(2 )
5
4
(0, - )(1 ) 2
2
1
O
B (4, A )(2 ) T
5
3 7
1
4
4
C E
(4, - )(1 )
Iteracin 03: convertimo en permanente el nodo C y actualizamos

(2, - )(1 ) 7 (9, A )(2 )


A D
5
2
4
(0, - )(1 ) 2
1
O B (4, A )(2 ) T
5
3 7
1
4
4
C E
(4, - )(1 ) (8, C)(3 )

Iteracin 04: convertimo en permanente el nodo B y actualizamos

(2, - )(1 ) 7 (8, B )(4 )


A D
5
2
4
(0, - )(1 ) 2
1
O B (4, A )(2 ) T
5
3 7
1
4
4
C E
(4, - )(1 ) (7, B)(4 )
Iteracin 05: convertimo en permanente el nodo E y actualizamos

(2, - )(1 ) 7 (8, B )(4 )


A D
5
2
4
(0, - )(1 ) 2
1
O B (4, A )(2 ) T
5
3 7
1
4 (14, E)(5 )
4
C E
(4, - )(1 ) (7, B)(4 )

Iteracin 06: convertimo en permanente el nodo D y actualizamos

(2, - )(1 ) 7 (8, B )(4 )


A D
5
2
4
(0, - )(1 ) 2
(13, D)(6 )
1
O B (4, A )(2 ) T
5
3 7
1
4
4
C E
(4, - )(1 ) (7, B)(4 )

Al convertir permanente al ltimo nodo nos indica que hemos encontrado la solucin ptima, es
decir la ruta ms corta
La ruta con distancia mnima de O hasta T es de 13u. Lo determinamos ahora de atrs hacia
adelante, el cual se ha encontrado con 6 iteraciones. O-A-B-D-T

También podría gustarte