floyd warshall (real problem)

UMSNH FIEAnálisis de Algoritmos Dra. Karina Mariela Figueroa Mora

Algoritmo de Floyd - Warshall

Herrera Garcia Jose Juanjjuan_hg@ieee.org

Problema

El problema surge por la necesidad de encontrar el camino mas corto y menos costoso para poder obtener mejores ganacias y ahorrar el mayor tiempo posible. Aplicados por ejemplo a el diseño de rutas de transporte, aproximaciones al problema del viajante de comercio, etc.

Algoritmo de Floyd - Warshall

8 de junio de 1936 en Nueva York a 25 de septiembre de 2001

El algoritmo de Floyd-Warshall Encuentra el camino más corto entre todos los pares de nodos o vértices de un grafo. Usa la metodología de Programación Dinámica para resolver el problema.

Robert W. Floyd

Entrada: una matriz de adyacencia n×n.

Cuerpo: la idea es Mantener una matriz con las distancias calculadas hasta ese momento.

Resultado: la matriz de resultados contendrá las distancias mínimas y el recorrido.

Problema Real

La Empresa cuenta con 7 bodegas distribuidoras de aguacate en el país. Los administradores desean saber el costo mínimos de flete de una bodega a otra sin importar la bodega que envía y la bodega que recibe, esto para optimizar recursos a la hora que se transporta producto.

Del Grafo obtenemos:

Aplicando el Algoritmo de Floyd-Warshall

Se obtiene la siguiente matriz

Aplicando el Algoritmo de Floyd-Warshall

Por ejemplo, si se quiere llevar producto de bodega A a la bodega G:

DAG= 55 Con el recorrido A E G

DAE = 35 Con el recorrido A D E

DAD = 20 Con el recorrido A B D

A B D E G

A B D E G

Aplicando el Algoritmo de Floyd-Warshall

Por ejemplo, si se quiere llevar producto de bodega A a la bodega G:

DFA= 40 Con el recorrido F D A

DDA = 20 Con el recorrido D B A

F D B A

F D B A

Complejidad del algortimo Floyd-Warshall

Pseducódigo:

FloydWarshall (camino[][]) {

N=camino.length;

para k: = 0 hasta N 1 − //N

para i:=0 hasta N 1− //N

Para j:=0 hasta N 1 − //N

camino[i][j] = mín ( camino[i][j], camino[i][k]+camino[k][j]);

}

N*N*N = N3 por lo tanto la complejidad de este algoritmo es O(N3).

Donde N es el número de nodos del grafo.

Complejidad usando fuerza bruta.

Ejemplo:

Para 4 nodos, los posibles caminos son:

(N-1)!=(3)!=6

Estos caminos son: