floyd warshall (real problem)
TRANSCRIPT
UMSNH FIEAnálisis de Algoritmos Dra. Karina Mariela Figueroa Mora
Algoritmo de Floyd - Warshall
Herrera Garcia Jose [email protected]
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:
