Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Algoritmo de Floyd-Warshall
144
Algoritmo de Floyd.
Eunice Diaz Seña.
Mariana Velásquez Hurtado.
Presentado a Esp. Jose Waldo de la Ossa.
Agenda.
Agenda.
- ¿Qué es el algoritmo de Floyd?
- Generalidades.
- Caracteristicas.
- Pasos.
- Ejemplo.
- Aplicabilidad en la vida cotidiana.
ALGORITMO DE FLOYD
¿Qué es el algoritmo de Floyd?
Es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución.
Tomado de: https://es.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall
Generalidades
- Su objetivo encontrar el camino más corto.
- El algoritmo de Floyd-Warshall compara todos los posibles caminos a través del grafo entre cada par de vértices.
Generalidades
CARACTERISTICAS
CARACTERISTICAS
- Trabaja con grafos ponderados. Es decir, el valor de la “flecha” que representamos en la matriz puede ser cualquier entero o infinito. Infinito marca que no existe unión entre los nodos. Esta vez, el resultado será una matriz donde estarán representadas las distancias mínimas entre nodos, seleccionando los caminos más convenientes según su ponderación (“peso”).
Los pasos del algoritmo de floyd son:
- 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 e i≠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.
PASOS
Ejemplo:
Ejemplo:
K=0
K=1
K=2
k=3
k=4
ANálisis de resultados.
Tabla de Camino más corto
Tabla de Recorridos
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.
APLICABILIDAD
APlICABILIDAD
Muchos problemas de la vida cotidiana se pueden expresar e incluso resolver en forma de grafo, por esto siempre que busquemos el camino mínimo en grafos dirigidos el algoritmo de Floyd nos sera muy útil.
GRACIAS...
GRACIAS...