Algoritmo de floyd

Algoritmo de Floyd: Este algoritmo es más general que el de Dijkstra, porque determina la ruta más corta entre cualesquiera dos nodos en la red. Representa una red de n nodos como una matriz cuadrada con n renglones y n columnas. La entrada (i,j) de la matriz de la distancia dij del nodo i al nodo j, que es finito si i está eslabonado directamente a j; de lo contrario es infinito.

La idea delalgoritmo de Floyd es directa. Dados tres nodos i, j y k donde las distancias de conexión se muestran en los tres arcos, es más corto llegar a k desde i a través de j si

dij + djk < dik

En este caso es óptimo reemplazar la ruta directa de i k con la ruta indirecta i j k. Este intercambio de triple operación se aplica sistemáticamente a la red utilizando lossiguientes pasos:

Paso 0. Defina la matriz de distancia inicial D0 y la matriz de secuencia del nodo S0. Los elementos diagonales están marcados con (-) para indicar que están bloqueados. Sea k = 1.

| |1 |2 |… |j |… |n |
|1 |- |d12 |… |d1j |… |d1n |
|2 |d21 |- |… |d2j |… |d2n |
|…|… |… |… |… |… |… |
|i |di1 |di2 |… |dij |… |din |
|… |… |… |… |… |… |… |
|n |dn1 |dn2 |… |dnj |… |- |

| |1 |2 |… |j |… |n |
|1 |- |2 |… |j |… |n |
|2 |1|- |… |j |… |n |
|… |… |… |… |… |… |… |
|i |1 |2 |… |j |… |n |
|… |… |… |… |… |… |… |
|n |1 |2 |… |j |… |- |

Paso general k.Defina el renglón k y la columna k como el renglón pivote y la columnapivote. Aplique la triple operación a cada elemento dij en Dk-1, para todas las i y j. Si se satisface la siguiente condición:

dik dkj < dij, (i ≠ k, j ≠ k y i ≠ j)

Realizando los siguientes cambios:
a) Cree Dk remplazando dij en Dk-1 con dik + dkj
b) Cree Sk reemplazando sij en Sk-1 con k. Determine k = k + 1 y repita el paso k.
El paso k del algoritmo se puedeexplicar con mayor facilidad representando Dk-1.
Acá en renglón k y la columna k definen el renglón y la columna pivote actuales. El renglón i representa cualquiera de los renglones 1,2,3,………,y k-1 y el renglón p representa cualquiera de los renglones k+1, k+2,……., y n. La triple operación se puede aplicar como sigue. Si la suma de los elementos en el renglón pivote y en la columna pivote (que semuestran por medio de cuadros) es menor que el elemento de la intersección asociada (que se muestra por medio de un círculo), entonces es óptimo reemplazar la distancia de la intersección por la suma de las distancias pivote.
Columna j Col. Pivote k Columna q

Renglón i

Renglón pivote k

Renglón p

Después de n pasos, se puede determinar la rutamás corta entre los nodos i y j desde las matrices Dn y Sn, utilizando las siguientes reglas:
1. Desde Dn, dij da la distancia más corta entre los nodos i y j.
2. Desde Sn, determine el nodo intermedio k=sij, que da la ruta i k j. Si sij = k y Sjk = j, deténgase; todos los nodos intermedios de la ruta han sido encontrados. De lo contrario, repita el procedimiento entre losnodos i y k y los nodos k y j.

Ejemplo:

Para la red, en la figura, encuentre las rutas más cortas entre cada dos nodos. Las distancias (en millas) se dan en los arcos. El arco (3,5) es direccional, de manera que no está permitido ningún tráfico del nodo 5 al nodo 3. Todos los demás arcos permiten el tráfico en ambas direcciones.

Iteración 0. Las matrices D0 y S0 dan la representación...