•          Problema: Calcular los caminos mínimos entre todos los pares de nodos del grafo.        

                Posibilidades

•          Aplicar el algoritmo de Dijkstra n veces, una por cada posible nodo origen:

–         Con matrices de adyacencia: O(n³)

–         Con listas de adyacencia: O(a·n·log n)

•          Aplicar el algoritmo de Floyd:

–         Con listas o matrices: O(n³)

Pero más sencillo de programar...

 

•  Entrada:

        C: array [1..n, 1..n] de real → Matriz de costos

•  Salida:

        D: array [1..n, 1..n] de reales → Costos caminos mínimos

               

Algoritmo de Floyd

                D:= C

                para k:= 1, ..., n hacer

                                para i:= 1, ..., n hacer

                                               para j:= 1, ..., n hacer

                                                    D[i, j]:= min ( D[i, j] , D[i, k] + D[k, j] )

 

•          ¿En qué se basa el algoritmo de Floyd?

•          En cada paso k, la matriz D almacena los caminos mínimos entre todos los pares pudiendo pasar por los k primeros nodos.

•          Inicialización: D almacena los caminos directos.

•          Paso 1: Caminos mínimos pudiendo pasar por el 1.

•          ...

•          Paso n: Caminos mínimos pudiendo pasar por cualquier nodo → Lo que buscamos.

•          En el paso k, el nodo k actúa de pivote.

•  Camino mínimo entre i y j, en el paso k:

        – Sin pasar por k: D[i, j]

        – Pasando por k: D[i, k] + D[k, j]

        – Nos quedamos con el menor.

•  Ojo: Falta indicar cuáles son los caminos mínimos.

•  P: array [1..n, 1..n] de entero. P[i, j] indica un nodo intermedio en el camino de i a j.

i → ... → P[i, j] → ... → j

 

Algoritmo de Floyd

                D:= C

                P:= 0

                para k:= 1, ..., n hacer

                                para i:= 1, ..., n hacer

                                               para j:= 1, ..., n hacer

                                                    si D[i, k] + D[k, j] < D[i, j] entonces

                                                               D[i, j]:= D[i, k] + D[k, j]

                                                               P[i, j]:= k

                                                    finsi

Analizar y responder la siguiente pregunta.

          ¿Cuánto es el orden de complejidad del algoritmo?

•          El algoritmo de Floyd se basa en una descomposición recurrente del problema:

•          Como la fila y columna k no cambian en el paso k, se usa una sola matriz D.

•          ¿Cómo recuperar el camino?

                               operación camino (i, j: entero)

                                               k:= P[i, j]

                                               si k ≠ 0 entonces

                                                   camino (i, k)

                                                   escribe (k)

                                                   camino (k, j)

                                               finsi

Consultar el siguiente Link:

https://elibro.bibliotecabuap.elogim.com/es/ereader/bibliotecasbuap/50117?page=499