Scribd
Cargar
23 vistas1 página

Algoritmo de Floyd: Ruta Más Corta

El algoritmo de Floyd es más eficiente que el de Dijkstra para encontrar rutas y distancias más cortas entre cualquier par de nodos. Se utiliza una tabla inicial de distancias y otra de recorridos, que se actualizan iterativamente para reflejar las mejoras en las distancias. Finalmente, se obtiene la trayectoria y la distancia total utilizando las matrices resultantes.

Cargado por

callejad496
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
23 vistas1 página

Algoritmo de Floyd: Ruta Más Corta

El algoritmo de Floyd es más eficiente que el de Dijkstra para encontrar rutas y distancias más cortas entre cualquier par de nodos. Se utiliza una tabla inicial de distancias y otra de recorridos, que se actualizan iterativamente para reflejar las mejoras en las distancias. Finalmente, se obtiene la trayectoria y la distancia total utilizando las matrices resultantes.

Cargado por

callejad496
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

2.2.

PROBLEMA DE LA RUTA MÁS CORTA 51

2.2.2. Algoritmo de Floyd


Este algoritmo es más eficiente que el algoritmo de Dijkstra, ya que permite encontrar la ruta y distancia
más corta entre cualquier par de nodos. El procedimiento de cálculo se adecua mejor para realizarse en
la computadora, es el algoritmo que se utilizó en el sofware IOpeTec.

Paso 1. Se forma una tabla inicial de distancias d (i , j ) de cada nodo i a cada nodo j , denominada D k ,
donde:

 distancia de i a j si existe arco(i , j )
d (i , j ) = − si i = j

∞ si no existe arco(i , j )

Así también se forma una tabla inicial de recorrido de cada nodo i a cada nodo j , denominada R k , donde:
½
0 para i =
6 j
r (i , j ) =
− para i = j

Paso 2. Se actualiza cada tabla para cada nodo k recorriendo todos los nodos de la red. La actualización
para el k − ési mo nodo o iteración se obtiene con la fórmula (en la iteración k no considerar i = j = k).
© ª
d (i , j ) = min d (i , j ), d (i , k) + d (k, j )

Con d i j igual a la longitud del camino más corto de i a j y nodos intermedios k. Si d (i , k) + d (k, j ) es
menor que d (i , j ), significa que se mejora la distancia de i a j y por lo tanto la matriz de distancias D k de
la iteración k, se sustituye con la distancia d (i , k) + d (k, j ) y se marca en negrita.

Si d (i , k)+d (k, j ) es menor que d (i , j ), significa que se mejora la distancia de i a j y por lo tanto la matriz
de recorrido R k de la iteración k, se sustituye con el valor de la iteración k.

Paso 3. Obtener la trayectoria de algún camino desde i hasta j , de manera recursiva mediante la siguiente
fórmula:
ruta(i , j ) = ruta(i , vi a) + ruta(vi a, j )
Donde vi a se obtiene de la matriz final de recorrido R k . Si ruta(i , j ), ruta(i , vi a) o ruta(vi a, j ) es igual a
cero, se ha llegado a la trayectoria, de lo contrario continuar de manera recursiva.

Paso 4. Obtener la distancia total de la trayectoria, en la última matriz de distancias D k .

Ejemplo 2.3 Aplicar el algoritmo de Floyd a la red de la figura 2.5. Los arcos (2, 5), (4, 3) y (7, 4) son
unidireccionales. Determinar la ruta más corta entre los siguientes pares de nodos:

1. Del nodo 1 al 7

2. Del nodo 3 al 5

Desarrollo del algoritmo:

También podría gustarte