6 Modelo de redes se satisface, realice los siguientes cambios: a.
Cree Dk reemplazando dij en
Dk21 con dik 1 dkj. b. Cree Sk reemplazando sij en Sk21 con k. Establezca k 5 k 1 1. Si k 5 n 1 1,
deténgase: de lo contrario repita el paso k. El paso k del algoritmo puede explicarse
representando Dk21 como se muestra en la figura [Link]í, la fila k y la columna k definen la
fila y columna pivote actuales. La fila i representa cualquiera de las filas 1, 2,…, y k 2 1, y la fila
p representa cualquiera de las filas k 1 1, k 1 2,…, y n. Asimismo, la columna j representa
cualquiera de las columnas 1, 2,…, y k 2 1, y la columna q representa cualquiera de las
columnas k 1 1, k 1 2,…, y n. La operación triple puede aplicarse como sigue: Si la suma de los
elementos en la fila pivote y la columna (mostrados por cuadrados) es menor que el elemento
de intersección asociado (mostrado por un círculo), entonces es óptimo reemplazar la
distancia de intersección por la suma de las distancias pivote. Después de n pasos, podemos
determinar la ruta más corta entre los nodos i y j a partir de las matrices Dn y Sn aplicando las
siguientes reglas: 1. dij, a partir de Dn, da la ruta más corta entre los nodos i y j. 2. A partir de
Sn, determine el nodo intermedio k 5 sij que da en resultado la ruta i S k S j. Si sik 5 k y skj 5 j,
deténgase; todos los nodos intermedios de la ruta han sido encontrados. De lo contrario,
repita el procedimiento entre los nodos i y k y entre los nodos k y j. Ejemplo 6.3-5 Para la red
de la figura 6.21, halle las rutas más cortas entre cada dos nodos. Las distancias (en millas) se
dan en los arcos. El arco (3,5) es direccional, es decir, no se permite el tráfico del nodo 5 al
nodo 3. Todos los demás arcos permiten el tráfico en dos direcciones. FIGURA 6.20
Implementación de la operación triple en forma de matriz dij dik diq Columna j Columna q
Columna pivote k dpj dpk dpq dkj Fila i Fila p Fila pivote k dkq [Link] 6.3
Problema de la ruta más corta 227 Iteración 0. Las matrices D0 y S0 dan la representación
inicial de la red. D0 es simétrica, excepto que d53 5 q porque no se permite tráfico del nodo 5
al nodo 3. D0 S0 123 45 1 2 3 45 1 — 3 10 q q 1— 2 3 4 5 2 3— q 5 q 21—3 45 3 10 q — 6 15 3
1 2 — 4 5 4 q 5 6 — 4 4 1 2 3 —5 5 qqq 4 — 5 1 2 3 4— D1 S1 123 45 1 2 3 45 1 — 3 10 q q 1—
2 3 4 5 2 3— 13 5 q 21— 1 4 5 3 10 13 — 6 15 3 1 1 —45 4 q 5 6 — 4 4 1 2 3 —5 5 qqq 4 — 5 1
2 3 4— Iteración 1. Establezca k 5 1. La fila y columna pivotes se muestran por la primera fila y
la primera columna ligeramente sombreadas en la matriz D0. Las celdas más oscuras, d23 y
d32, son las únicas que la operación triple puede mejorar. Por lo tanto, D1 y S1 se obtienen
desde D0 y S0 como sigue: 1. Reemplace d23 con d21 1 d13 5 3 1 10 5 13 y establezca s23 5 1.
2. Reemplace d32 con d31 1 d12 5 10 1 3 5 13 y establezca s32 5 1. Estos cambios se muestran
en negritas en las matrices D1 y S1. FIGURA 6.21 Red para el ejemplo 6.3-5 2 5 4 4 10 15 6 3 1 5
3 D2 S2 123 45 1 2 3 45 1 — 3 10 8 q 1— 2 3 2 5 2 3 — 13 5 q 21—1 45 3 10 13 — 6 15 3 1 1 —
4 5 4 8 5 6— 4 4 2 2 3 —5 5 qqq 4 — 5 1 2 3 4— Iteración 2. Establezca k 5 2, como se muestra
mediante la fila y columna ligeramente sombreada en D1. La operación triple se aplica a las
celdas más oscuras en D1 y S1. Los cambios resultantes se muestran en negritas en D2 y S2.
[Link] 228 Capítulo 6 Modelo de redes Iteración 4. Establezca k 5 4, como se
muestra por la fila y columna sombreadas en D3. Las nuevas matrices son D4 y S4. Iteración 5.
Establezca k 5 5, como se muestra mediante la fila y columna sombreadas en D4. No son
posibles más mejoras en esta iteración. Las matrices finales D4 y S4 contienen toda la
información necesaria para determinar la ruta más corta entre dos nodos cualesquiera en la
red. Por ejemplo, desde D4, la distancia más corta del nodo 1 al nodo 5 es d15 5 12 millas. Para
determinar la ruta asociada, recordemos que un segmento (i,j) representa un vínculo directo
sólo si sij 5 j. De lo contrario, i y j están vinculaD4 S4 123 45 1 2 3 45 1 — 3 10 8 12 1— 2 3 2 4 2
3— 11 5 9 21— 4 4 4 3 10 11 — 6 10 3 1 4 — 4 4 4 8 5 6— 4 4 2 2 3 —5 5 12 9 10 4— 5 444 4 —
D3 S3 123 45 1 2 3 45 1 — 3 10 8 25 1— 2 3 2 3 2 3 — 13 5 28 21—1 4 3 3 10 13 — 6 15 3 1 1
— 4 5 4 8 5 6 — 4 4 2 2 3 —5 5 qqq 4 — 5 1 2 3 4— Iteración 3. Establezca k 5 3, como se
muestra por la fila y columna sombreadas en D2. Las nuevas matrices son D3 y S3. dos por al
menos otro nodo intermedio. Como s15 5 4 Z 5, la ruta inicialmente se da como 1 S 4 S 5.
Ahora, como s14 5 2 p 4, el segmento (1,4) no es un vínculo directo, y 1 S 2 S 4 reemplaza a 1 S
4, y la ruta 1 S 4 S 5 ahora se vuelve 1 S 2 S 4 S 5. Luego, como s12 5 2, s24 5 4, y s45 5 5, no se
requieren más “disecciones”, y 1 S 2 S 4 S 5 define la ruta más corta. Momento de TORA Como
en el algoritmo de Dijkstra, TORA puede usarse para generar las iteraciones de Floyd. En el
menú seleccione las opciones . El archivo [Link] proporciona los datos para el ejemplo
6.3-5. CONJUNTO DE PROBLEMAS 6.3C 1. En el ejemplo 6.3-5, use el algoritmo de Floyd para
determinar las rutas más cortas entre cada uno de los siguientes pares de nodos: *(a) Del nodo
5 al nodo 1. (b) Del nodo 3 al nodo 5. Floyd’s algorithm SOLVE/MODIFY Solve problem Q
Iterations Q [Link] 6.3 Problema de la ruta más corta 229 (c) Del nodo 5 al nodo
3. (d) Del nodo 5 al nodo 2. 2. Aplique el algoritmo de Floyd a la red de la figura 6.22. Los arcos
(7,6) y (6,4) son unidireccionales, y todas las distancias están en millas. Determine la ruta más
corta entre los siguientes pares de nodos: (a) Del nodo 1 al nodo 7. (b) Del nodo 7 al nodo 1. (c)
Del nodo 6 al nodo 7. 3. La compañía de telefonía celular Te