Operativa IIMODELO DE REDES

FRANCISCO VARGASINGENIERO DE SISTEMAS

ESPECIALISTA EN GERENCIA DE SISTEMAS INFORMÁTICOSMAGÍSTER EN CIENCIAS DE LA INFORMACIÓN Y LAS COMUNICACIONES CON ÉNFASIS EN

TELEINFORMÁTICACANDIDATO A DOCTOR EN CIENCIA Y TECNOLOGÍA INFORMÁTICA

2015

MODELO DE REDES

3. MODELO DE LA RUTA MAS CORTA

Red acíclica: No contiene lazosRed cíclica: Contiene lazos

3.2 Algoritmo acíclico:

dij

Sumidero o destino

Inicial

Uj Distancia más corta entre el nodo 1 y el nodo j

Figura 3.

3.1 Tipos de redes: De acuerdo a su estructura se presenta una tipificación de las mismas, la cual se puede observar a continuación:

MODELO DE REDES

Uj Se calcula en forma recursiva por medio de la siguiente fórmula:

Uj = mín i

La distancia Ui más corta a un nodo i inmediatamente anterior más

La distancia dij entre el nodo actual j y su predecesor i

Uj = mín Ui + dij i

Procedimiento de etiquetado o de rotulación: etiqueta del nodo j = Uj , nn Nodo que precede inmediatamente a j

Uj = mín Ui + dij i = Un + dnj

Ejemplo: 0,- Etiqueta del nodo 1, indicando que es el nodo fuente.

MODELO DE REDES

3.3 Ejemplo de algoritmo acíclico

Los cálculos se pueden resumir en una tabla tal como se ilustra en la tabla 1 o en la figura de la red directamente, como se ilustra en la figura 3.

(7) 13,5 (5) 7,2 (2) 2,1 (1)Ruta óptima

MODELO DE REDES

3.4 Algoritmo cíclico (de Dijkstra)

• El algoritmo acíclico no funciona de forma correcta con redes que posean lazos dirigidos (circuitos).

• Usa dos tipos de etiquetas : Temporal y permanente; formato de las dos etiquetas

d,n d distancia más corta disponible hasta el momento, a un nodo desde el origen n es el nodo inmediato precedente al cual la distancia es igual a d Nodo fuente que lleva etiqueta

0,-

Consideramos todos los nodos que se pueden alcanzar directamente desde el nodo fuente y determinamos sus etiquetas asociadas.

Las etiquetas recién creadas se designan como temporales

La siguiente etiqueta permanente se selecciona como aquella , de entre las etiquetas temporales corrientes , que tenga la menor d en la etiqueta d,n (los empates se rompen

arbitrariamente)El proceso se repite para el último nodo que se ha designado permanente. En tal caso, una etiqueta temporal de un nodo se puede cambiar solo si la nueva etiqueta da una distancia d menor.

Inicio

Fin

MODELO DE REDES

3.5 Procedimiento: A continuación se detalla el procedimiento basado en el algoritmo, a través de un ejemplo.

Aplicar el procedimiento a la red en la figura 4.

Figura 4.

3.6 Ejemplo de algoritmo de Dijkstra

MODELO DE REDES

Aplicar el procedimiento a la red en la figura 4.

MODELO DE REDES

La siguiente figura 5 muestra la solución.

MODELO DE REDES

3.7 Ejercicios de Aplicación

1. Encontrar la distancia más corta entre el nodo A y el nodo G

2. Encontrar la distancia más corta entre el nodo 1 y el nodo 9

MODELO DE REDES

Ejercicio. El siguiente ejemplo se desarrollará con el fin de encontrar el camino más corto desde 1 hasta 4:

Ejercicio. El siguiente ejemplo se desarrollará con el fin de encontrar el camino más corto desde 1 hasta 8:

3.7 Ejercicios de Aplicación