Redes

Algoritmo de la ruta más corta

Algoritmo Dijkstra

Algoritmo de Floyd

Algoritmo de Floyd

Redes
A. Cano M.
IC Y F

11 de junio 2012

A. Cano M. Redes

Ingeniería Comercial y Financiera

Algoritmo de la ruta más corta

Algoritmo Dijkstra

Algoritmo de Floyd

Algoritmo de Floyd

Algoritmos ruta más corta

Dijkstra tiene por objeto dterminar las rutas más cortas entreel nodo fuente y todos los demás nodos de la red. Floyd es general, porque permite determinar la ruta más corta entre 2 nodos cualquiera en la red.

A. Cano M. Redes

Ingeniería Comercial y Financiera

Algoritmo de la ruta más corta

Algoritmo Dijkstra

Algoritmo de Floyd

Algoritmo de Floyd

Etiqueta de un nodo Sea ui la distancia más corta del nodo fuente 1 hacia el nodo i, y sedefine dij (≥ 0) como la longitud del arco (i, j). Entonces el algoritmo define la etiqueta de un nodo inmediato posterior j como [uj , i] = [ui + dij , i] ; dij ≥ 0 La etiqueta del nodo de inicio es [0, −], que indica que el nodo no tiene predecesor. Las etiquetas de nodos en el algoritmo de Dijkstra son de 2 clases: Temporales y Permanentes. Una etiqueta temporal se modifica si se puede encontraruna ruta más corta a un nodo. Cuando se ve que no se pueden encontrar rutas mejores, cambia el estado de la etiqueta temporal a permanente.

A. Cano M. Redes

Ingeniería Comercial y Financiera

Algoritmo de la ruta más corta

Algoritmo Dijkstra

Algoritmo de Floyd

Algoritmo de Floyd

Algoritmo de Dejkstra Paso 0 Etiquetar el nodo fuente (nodo 1) [0, −] con la etiqueta permanente eigualar i = 1. Paso i (a) Calcular las etiquetas temporaes [u1 + dij , i] para cada nodo j al que pueda llegarse etiquetado con [uj , k] por otro nodo k, y si ui + dij < uj , sustituir [uj , k] por [uj + dij , i]. (b) Si todos los nodos tienen etiquetas permanentes, detenerse. En caso contrario, seleccionar la etiqueta [ur , s] que tenga distancia más corta (= ur ) entre todas las etiquetastemporales (los empates se rompen en forma arbitraria). Hacer que i = r y Ingeniería Comercial y Financiera repetir el paso i.

A. Cano M. Redes

Algoritmo de la ruta más corta

Algoritmo Dijkstra

Algoritmo de Floyd

Algoritmo de Floyd

Ejemplo La rede de la figura muestra las rutas con sus longitudes, en millas, entre la ciudad 1 y otras 4 ciudades. Determina la ruta más corta entre laciudad 1 y cada una de las 4 ciudades restantes.

2 100 20

15 4 10 50

1 30

3 60

5

A. Cano M. Redes

Ingeniería Comercial y Financiera

Algoritmo de la ruta más corta

Algoritmo Dijkstra

Algoritmo de Floyd

Algoritmo de Floyd

Solución
Iteración 1 Nodo 1 2 3 Etiqueta [0, −] [0 + 100, 1] = [100, 1] [0 + 30, 1] = [30, 1]
Table: Iteración 1

Estado Permanente TemporalTemporal

De las 2 etiquetas temporales, el nodo 3 produce la menor distancia (uj = 30). Entonces, se cambia el estado de nodo 3 a permanente.
A. Cano M. Redes Ingeniería Comercial y Financiera

Algoritmo de la ruta más corta

Algoritmo Dijkstra

Algoritmo de Floyd

Algoritmo de Floyd

Solución
Iteración 2 Nodo 1 2 3 4 5 Etiqueta [0, −] [100, 1] [30, 1] [30 + 10, 3] = [40, 3] [30 + 60,3] = [90, 3]
Table: Iteración 2

Estado Permanente Temporal Permanente Temporal Temporal

el nodo 4 produce la menor distancia (u3 = 40), entonces se cambia el estado del nodo 4.
A. Cano M. Redes Ingeniería Comercial y Financiera

Algoritmo de la ruta más corta

Algoritmo Dijkstra

Algoritmo de Floyd

Algoritmo de Floyd

Solución
Iteración 3 Nodo 1 2 3 4 5 Etiqueta [0, −] [40 +15, 4] = [55, 4] [30, 1] [40, 3] [40 + 50, 4] = [90, 4] Estado Permanente Temporal Permanente Permanente Temporal

Table: Iteración 3

La etiqueta temporal del nodo 2, [100, 1], en la iteración 2 se cambia a [55, 3] en la iteración 3, para indicar que se ha encontrado una ruta más corta que pasa por el nodo 4. A. Cano M. Ingeniería También, en la iteración 3, el nodo 5 tiene 2 etiquetas...