ALGORITMO DE FLOYD EJEMPLO

PROBLEMA DE LA RUTA MAS CORTA

ALGORTIMO DE FLOYD

El algoritmo de Floyd es más general que el de Dijkstra, ya que determina la ruta más corta entre dos nodos cualquiera de la red.

• El algoritmo representa una red de n nodos como una matriz cuadrada de orden n, la llamaremos matriz C. De esta forma, el valor Cij representa el coste de ir desde el nodo i al nodo j, inicialmente en caso de no existir un arco entre ambos, el valor Cijserá infinito.

• Definiremos otra matriz D, también cuadrada de orden n, cuyos elementos van a ser los nodos predecesores en el camino hacia el nodo origen, es decir, el valor Dijrepresentará el nodo predecesor a j en el camino mínimo desde i hasta j. Inicialmente se comienza con caminos de longitud 1, por lo que Dij = i.

• Las diagonales de ambas matrices representan el coste y el nodo predecesor para ir de un nodo a si mismo, por lo que no sirven para nada, estarán bloqueadas.

Los pasos a dar en la aplicación del algoritmo de Floyd son los siguientes:

• Formar las matrices iniciales C y D.

• Se toma k=1.

• Se selecciona la fila y la columna k de la matriz C y entonces, para i y j, con i≠k, j≠k ei≠j, hacemos:

Si (Cik + Ckj) < Cij → Dij = Dkj y Cij = Cik + Ckj

En caso contrario, dejamos las matrices como están.

• Si k ≤ n, aumentamos k en una unidad y repetimos el paso anterior, en caso contrario paramos las iteraciones.

• La matriz final C contiene los costes óptimos para ir de un vértice a otro, mientras que la matriz D contiene los penúltimos vértices de los caminos óptimos que unen dos vértices, lo cual permite reconstruir cualquier camino óptimo para ir de un vértice a otro.

PROBLEMA:

Juan Carlos quiere llegar lo más rápido posible a su trabajo para ello deberá escoger la ruta que debe tomar el autobús para recorrer la menor distancia y llegar a tiempo a su trabajo. El diagrama de las rutas es el siguiente. Las distancias están dadas en km.

SOLUCION MANUAL:

MATRIZ C MATRIZ D

1 2 3 4 5 6 1 2 3 4 5 6

1 - 29 37 ∞ ∞ ∞ 1 - 1 1 ∞ ∞ ∞

2 ∞ - 20 22 ∞ ∞ 2 ∞ - 2 2 ∞ ∞

3 ∞ ∞ - 32 34 ∞ 3 ∞ ∞ - 3 3 ∞

4 ∞ ∞ ∞ - 43 34 4 ∞ ∞ ∞ - 4 4

5 ∞ ∞ ∞ ∞ - 26 5 ∞ ∞ ∞ ∞ - 5

6 ∞ ∞ ∞ ∞ ∞ - 6 ∞ ∞ ∞ ∞ ∞ -

Tomamos k=1

Tomamos i=2 (i ≠k):

• j=3 (j≠k, j≠i): C[2,1]+C[1,3] = ∞+37 = ∞, no hay que cambiar nada, no podemos llegar de 2 a 3 a través de 1.

• j=4 (j≠k, j≠i): C[2,1]+C[1,4] = ∞+∞ = ∞ ,no hay que cambiar nada, no podemos llegar de 2 a 4 a través de 1.

• j=5 (j≠k, j≠i): C[2,1]+C[1,5] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 2 a 5 a través de 1.

• j=6 (j≠k, j≠i): C[2,1]+C[1,6] = ∞+∞ = ∞ ,no hay que cambiar nada, no podemos llegar de 2 a 6 a través de 1.

• Tomamos i=3 (i ≠k):

• j=2 (j≠k, j≠i): C[3,1]+C[1,2] = ∞+29 = ∞ , no hay que cambiar nada, no podemos llegar de 3 a 2 a través de 1.

• j=4 (j≠k, j≠i): C[3,1]+C[1,4] = ∞+∞ = ∞ , no hay que cambiar nada, no podemos llegar de 3 a 4 a través de 1.

• j=5 (j≠k, j≠i): C[3,1]+C[1,5] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 3 a 5 a través de 1.

• j=6 (j≠k, j≠i): C[3,1]+C[1,6] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 3 a 6 a través de 1.

• Tomamos i=4 (i ≠k):

• j=2 (j≠k, j≠i): C[4,1]+C[1,2] = ∞+29 = ∞, no hay que cambiar nada, no podemos llegar de 4 a 2 a través de 1.

• j=3 (j≠k, j≠i): C[4,1]+C[1,3] = ∞+37 = ∞, no hay que cambiar nada, no podemos llegar de 4 a 3 a través de 1.

• j=5 (j≠k, j≠i): C[4,1]+C[1,5] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 4 a 5 a través de 1.

• j=6 (j≠k, j≠i): C[4,1]+C[1,6] = ∞+∞= ∞, no hay que cambiar nada, no podemos llegar de 4 a 6 a través de 1.

•

• Tomamos i=5 (i ≠k):

• j=2 (j≠k, j≠i): C[5,1]+C[1,2] = ∞+29 = ∞, no hay que cambiar nada, no podemos llegar de 5 a 2 a través de 1.

• j=3 (j≠k, j≠i): C[5,1]+C[1,3] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 5 a 3 a través de 1.

• j=4 (j≠k, j≠i): C[5,1]+C[1,4] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 5 a 4 a través de 1.

• j=6 (j≠k, j≠i): C[5,1]+C[1,6] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 5 a 6 a través de 1.

• Tomamos i=6 (i ≠k):

• j=2 (j≠k, j≠i): C[6,1]+C[1,2] = ∞+29 = ∞, no hay que cambiar nada, no podemos llegar de 6 a 2 a través de 1.

• j=3 (j≠k, j≠i): C[6,1]+C[1,3] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 6 a 3 a través de 1.

• j=4 (j≠k, j≠i): C[6,1]+C[1,4] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 6 a 4 a través de 1.

• j=5 (j≠k, j≠i): C[6,1]+C[1,5] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 6 a 5 a través de 1.

MATRIZ C MATRIZ D

1 2 3 4 5 6 1 2 3 4 5 6

1 - 29 37 ∞ ∞ ∞ 1 - 1 1 ∞ ∞ ∞

2 ∞ - 20 22 ∞ ∞ 2 ∞ - 2 2 ∞ ∞

3 ∞ ∞ - 32 34 ∞ 3 ∞ ∞ - 3 3 ∞

4 ∞ ∞ ∞ - 43 34 4 ∞ ∞ ∞ - 4 4

5 ∞ ∞ ∞ ∞ - 26 5 ∞ ∞ ∞ ∞ - 5

6 ∞ ∞ ∞ ∞ ∞ - 6 ∞ ∞ ∞ ∞ ∞ -

Tomamos k=2

Tomamos i=1 (i ≠k):

• j=3 (j≠k, j≠i): C[1,2]+C[2,3] = 29+20 = 49 > C[1,3] = 37, no hay que cambiar nada, el camino es mayor que el existente.

• j=4 (j≠k, j≠i): C[1,2]+C[2,4] = 29+22 = 51 < C[2,3] = ∞, por tanto hacemos:

C[1,4] = 51 y D[1,4] = 2

• j=5 (j≠k, j≠i): C[1,2]+C[2,5] = 29+∞ = ∞, no hay que cambiar nada, no podemos llegar de 1 a 5 a través de 2.

• j=6 (j≠k, j≠i): C[1,2]+C[2,6] = 29+∞ = ∞, no hay que cambiar nada, no podemos llegar de 1 a 6 a través de 2.

• Tomamos i=3 (i ≠k):

• j=1 (j≠k, j≠i): C[3,2]+C[2,1] = ∞+∞= ∞, no hay que cambiar nada, no podemos llegar de 3 a 1 a través de 2.

• Debido a que C[3,2] = ∞ y se mantiene constante para j=1,4,5,6 no hay que cambiar nada

• Tomamos i=4 (i ≠k):

• j=1 (j≠k, j≠i): C[4,2]+C[2,1] = ∞+∞ = ∞, no hay que cambiar nada, no podemos llegar de 4 a 1 a través de 2.

...