1

Ejemplo de red para el algoritmo de la ruta más corta de Dijkstra 1 2 30 60 100 10 50 20 15 3 4
5 Para las dos etiquetas temporales [100,1] y [30,1], el nodo 3 da la distancia mínima (u3 5 30).
De este modo, el estado del nodo 3 cambia a permanente. Iteración 2. Se puede llegar a los
nodos 4 y 5 desde el nodo 3, y la lista de los nodos etiquetados es La etiqueta temporal [40,3]
en el nodo 4 ahora es permanente (u4 5 40). www.FreeLibros.com 6.3 Problema de la ruta más
corta 223 Iteración 3. Desde el nodo 4 se puede llegar a los nodos 2 y 5 Así, la lista de los nodos
etiquetados se actualiza como En el nodo 2, la nueva etiqueta [55,4] reemplaza a la etiqueta
temporal [100,1] de la iteración 1 porque proporciona una ruta más corta. Además, en la
iteración 3 el nodo 5 tiene dos etiquetas alternativas con la misma distancia (u5 5 90). La
etiqueta temporal [55,4] en el nodo 2 ahora es permanente (u2 5 55). Iteración 4. Sólo el nodo
3 permanentemente etiquetado puede ser alcanzado desde el nodo 2. Por consiguiente el
nodo 3 no puede ser reetiquetado. La nueva lista de etiquetas permanece como estaba en la
iteración 3 excepto que la etiqueta en el nodo 2 ahora es permanente. Esto deja al nodo 5
como la única etiqueta temporal. Como el nodo 5 no conduce a otros nodos, su etiqueta se
hace permanente, y el proceso termina. Los cálculos del algoritmo pueden realizarse
directamente en la red, como lo demuestra la figura 6.16. La ruta más corta entre el nodo 1 y
cualquier otro nodo en la red se determina partiendo del nodo destino deseado y
retrocediendo hasta el nodo de inicio utilizando la información en las etiquetas permanentes.
Por ejemplo, la siguiente secuencia determina la ruta más corta del nodo 1 al nodo 2: Por lo
tanto, la ruta deseada es 1 S 3 S 4 S 2 con una distancia total de 55 millas. (2) : [55, 4] : (4) : [40,
3] : (3) : [30, 1] : (1) Nodo Etiqueta Estado 1 [0, —] Permanente 2 [40 + 15, 4] = [55, 4]
Temporal 3 [30, 1] Permanente 4 [40, 3] Permanente 5 o[90, 3] [40 + 50, 4] = [90, 4] Temporal
1 2 [100,1](1) [55,4](3) [90,3](2) [90,4] [0,](1) (3) [30,1](1) [40,3](2) 30 60 100 ( ) iteración 10
50 20 15 3 4 5 FIGURA 6.16 Procedimiento de etiquetado en el algoritmo de Dijkstra
www.FreeLibros.com 224 Capítulo 6 Modelo de redes Momento de TORA Puede usarse TORA
para generar las iteraciones de Dijkstra. En el menú seleccione las opciones . El archivo
toraEx3- 4.txt proporciona los datos para el ejemplo 6.3-4. CONJUNTO DE PROBLEMAS 6.3B 1.
La red de la figura 6.17 presenta las distancias en millas entre pares de ciudades 1,2,…,8. Use el
algoritmo de Dijkstra para determinar la ruta más corta entre las siguientes ciudades: (a)
Ciudades 1 y 8 (b) Ciudades 1 y 6 *(c) Ciudades 4 y 8 (d) Ciudades 2 y 6 2. Utilice el algoritmo
de Dijkstra para hallar la ruta más corta entre el nodo 1 y cualquier otro nodo en la red de la
figura 6.18. 3. Utilice el algoritmo de Dijkstra para determinar la solución óptima de cada uno
de los siguientes problemas: (a) Problema 1, conjunto 6.3a. (b) Problema 2, conjunto 6.3a. (c)
Problema 4, conjunto 6.3a. Solve problem Q Iterations Q Dijkstra’s algorithm SOLVE/MODIFY
FIGURA 6.17 Red para el problema 1, conjunto 6.3b 2 4 7 8 1 5 4 5 8 1 1 1 7 5 2 2 2 2 6 3 6 3 3 6
FIGURA 6.18 Red para el problema 2, conjunto 6.3b 3 5 2 1 4 7 7 7 6 6 6 3 5 5 2 7 9 2 1 7 1 4 6
www.FreeLibros.com 6.3 Problema de la ruta más corta 225 Algoritmo de Floyd. Este
algoritmo es más general que el Dijkstra porque determina la distancia entre dos nodos
cualesquiera en la red. El algoritmo representa una red de n nodos como una matriz cuadrada
con n filas y n columnas. La entrada (i,j) de la matriz da la distancia dij del nodo i al nodo j, la
cual es finita si i está vinculado directamente a j, e infinita en caso contrario. La idea del
algoritmo de Floyd es simple. Dados tres nodos, i, j y k en la figura 6.19 con las distancias de
conexión que se muestran en los tres arcos, es más corto llegar de j a i pasando por k si En este
caso es óptimo reemplazar la ruta directa de i S j con la ruta indirecta i S k S j. Este intercambio
de operación triple se aplica a la matriz de distancias por medio de los siguientes pasos: Paso
0. Defina la matriz de la distancia de inicio D0 y la matriz de secuencia de nodos S0 (todos los
elementos en las diagonales están bloqueados). Establezca k 5 1. dik + dkj 6 dij FIGURA 6.19
Operación triple de Floyd i k j d dkj ik dij 1 2 Á j Á n 1 — d12 Á dij Á d1n 2 d21 — Á d2j Á d2n oo
o o o o o D0 = I di1 di2 Á dij Á din oo o o o o o N Dn1 dn2 Á dnj Á - 1 2 Á j Á n 1— 2 Á j Á n 21—
Á j Á n S0 = o ooo oo o i 1 2 Á j Á n o ooo oo o n 1 2 Á j Á — Paso general k. Defina la fila k y la
columna k como fila pivote y columna pivote. Aplique la operación triple a cada elemento dij
en Dk21, para todas las i y j. Si la condición dik + dkj 6 dij, (i Z k, j Z k,y i Z j)

1

Cargado por

Copyright:

Formatos disponibles

1

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

1

Cargado por

Copyright:

Formatos disponibles

Ejemplo de red para el algoritmo de la ruta más corta de Dijkstra 1 2 30 60 100 10 50 20 15 3 4

También podría gustarte