Want to make creations as awesome as this one?

Transcript

Next

Bienvenidosa a la exposición del equipo #1 Esperamos que sea de su agrado , sin mas por decir gracias por su presencia.

Algoritmo de Floyd-Warshall

Next

Equipo #1Vargas Muñoz Jovani Salmerón Villalba Kelly Judith Hernandez DelgadoFernando Saul

El algoritmo de Floyd-Warshall es la opción utilizada cuando se desea determinar el camino mínimo entre todos los pares de vértices de un grafo, comparando todos los posibles caminos logra mejorar paulatinamente la estimación hasta llegar a la más óptima. Esto puede presentarse de manera más clara a través de un ejemplo de implementación. Pero antes, revisaremos el análisis del tiempo de ejecución para este caso.

Análisis e implementación

Next

Al momento de analizar un algoritmo revisamos el conjunto de operaciones primitivas de alto nivel que son independientes del lenguaje de programación que se utilice, estas pueden ser identificadas en el pseudocódigo del mismo.

Análisis del algoritmo

Next

Para ésto, revisamos cada paso del algoritmo en el pseudocódigo y contamos las operaciones que se ejecutan. A continuación se muestra el procedimiento llevado a cabo:

Conteo de operaciones primitivas

Next

Estimación del tiempo de ejecución

Ahora, calculamos el tiempo de ejecución t(n) del algoritmo Floyd-Warshall sumando el costo obtenido de las operaciones primitivas.

Next

Ahora daremos un ejemplo de su implementacion real.

Ya que sabemos lo teorico , sigue saber realemente como se usa por eso...

Next

Debido a la situación actual decides crear una red de entrega de suministros a domicilio para ayudar a los habitantes de la Ciudad de México. Decides comenzar operando únicamente en seis puntos geográficos, que puedes cubrir gracias a la facilidad de desplazarse entre ellos. Te interesa saber las rutas más cortas a seguir entre la ubicación del proveedor y la del cliente para cumplir con las entregas de la manera más óptima. Por ello, realizas el análisis para saber todas las posibles rutas que utilizarás.

Next

la descripción de los datos es lo primero a identificar

  • Matriz C = Es el conjunto de distancias entre cada par de puntos, algunos de ellos no cuentan con un camino directo al cual poder acceder (por lo que se agrega una distancia infinita para representarlo).
  • Matriz Z = Es la matriz de nodos antecesores, en donde cada elemento es el punto directo anterior con la distancia más corta, determina las rutas mínimas.
  • [i, j] = es la ubicación de un elemento en una matriz, donde i es la fila a la que pertenece y j la columna.
  • k = la iteración que se está llevando a cabo, para saber en qué parte del proceso nos encontramos.

Next

¿Qué caminos disponibles existen entre los puntos?

Next

Cada elemento [i, j] representa la distancia del punto i al punto j, que es finita si existe un camino e infinita en caso contrario. Iniciamos la matriz de nodos antecesores Z, donde se muestran las rutas que por ahora van desde el punto origen directamente hasta el destino.

Next

Next

Para agilisar la acción/tiempo, nos saltaremos el proceso ya que se logro explicar con claridad en el video e iremos directo al resultado.

Next

De lo anterior podemos decir que la matriz C nos muestra la distancia más corta entre cada par de nodos en la red original y la matriz Z indica la ruta a seguir desde i hasta j para que el recorrido sea eficiente. Podemos ver por ejemplo que entre el punto 1 y el 6 la distancia es de 900 y que la ruta a seguir pasa por el punto 3, sigue al 2 y termina en el 6.

Una vez que todos los procedimientos se hayan realizado , el resultado seria el siguiente.

Ahora, si queremos facilitar la implementación para otros casos en el futuro, sin pasar de nuevo por el proceso iterativo y las operaciones, implementar el algoritmo en un lenguaje de programación nos ahorraría bastante trabajo. A continuación se encuentra el código correspondiente en Python, usando los mismos datos que teníamos al comienzo pero obteniendo los resultados con menor esfuerzo.

Una pequeña recomendacion es que a través del uso de las matrices resultantes, se puede saber no solo la distancia mínima entre el punto de salida y el de llegada, sino también la ruta a utilizar. Esto podrá ahorrar tiempo y dinero en cada entrega, a la vez de maximizar el número de pedidos que pueden recibirse, por lo que considerar este plan de acción resultaría beneficioso para el negocio en todos los aspectos.

Next

Eso seria todo por nuestra parte , gracias por su atención<3

Ruedas, I. M. &. L. (2021, 29 diciembre). Algoritmo de Floyd-Warshall. Análisis e implementación | by Ingrid Mendoza & Luisa Ruedas | Análisis de algoritmos. Medium. https://medium.com/algoritmo-floyd-warshall/algoritmo-de-floyd-warshall-e1fd1a900d8

Bibliografía