Scribd
Cargar
46 vistas1 página

Rutas más cortas en redes mediante matrices

Este documento describe el algoritmo de Dijkstra para encontrar las rutas más cortas entre nodos en una red. Explica cómo el algoritmo itera a través de nodos pivote, actualizando las matrices D y S para rastrear las rutas más cortas entre todos los pares de nodos después de n iteraciones. Proporciona un ejemplo para ilustrar cómo aplicar el algoritmo para encontrar las rutas más cortas entre nodos en una red dada con distancias especificadas entre los arcos.

Cargado por

JHAMPIER ANCCASI HUAMAN
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
46 vistas1 página

Rutas más cortas en redes mediante matrices

Este documento describe el algoritmo de Dijkstra para encontrar las rutas más cortas entre nodos en una red. Explica cómo el algoritmo itera a través de nodos pivote, actualizando las matrices D y S para rastrear las rutas más cortas entre todos los pares de nodos después de n iteraciones. Proporciona un ejemplo para ilustrar cómo aplicar el algoritmo para encontrar las rutas más cortas entre nodos en una red dada con distancias especificadas entre los arcos.

Cargado por

JHAMPIER ANCCASI HUAMAN
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

226 Capítulo 6 Modelo de redes

Columna
Columna pivote Columna
j k q

Fila i dij dik diq

Fila pivote k dkj dkq

Fila p dpj dpk dpq FIGURA 6.20


Implementación de la operación
triple en forma de matriz

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 6.20.Aquí, 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 co-
lumnas 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 dis-
tancia 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.

También podría gustarte