Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmo de Floyd-Warshall

No description
by

Juan Diego Ramirez

on 12 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmo de Floyd-Warshall

Algoritmo de Floyd-Warshall
¿Quién lo creó?
El algoritmo de Floyd-Warshall ('All-Pairs-Shortest-Path' - Todos los caminos mínimos) fue ideado por Robert W. Floyd en 1962 basándose en un teorema de Warshall también de 1962.
Biografía
Robert W. Floyd nació el 8 de junio de 1936 en Nueva York, y murió el 25 de septiembre de 2001. Fue un prominente científico estadounidense en informática.
Floyd culminó el bachillerato a los 14 años. Se graduó en la Universidad de Chicago en 1953 a los 17 años y como Físico en 1958.

Fue nombrado profesor asociado en la Universidad de Carnegie Mellon. Seis años más tarde fue nombrado profesor en la Universidad de Stanford.
Entre sus contribuciones se encuentran el diseño y análisis de algoritmos eficientes para encontrar el camino más corto en un grafo y para el problema de reconocimiento de frases.

Floyd recibió el Premio Turing de la ACM en 1978 «por tener una clara influencia en las metodologías para la creación de software eficiente y confiable, y por haber contribuido a la fundación de las subáreas teoría del reconocimiento de frases, semántica de los lenguajes de programación, verificación automatizada de programas, síntesis automatizada de programas y análisis de algoritmos».
Matrices
Descripción
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 lo que garantiza que la solución entregada por este algoritmo sea óptima, además entrega todos los caminos más cortos para ir desde un nodo
i
hasta un nodo
j
cualquiera y el recorrido necesario.
Implementación
Este algoritmo se basa en lo siguiente: supongamos que tenemos la forma de llegar del vértice i al j de forma óptima contando con k-1 puntos intermedios. Ahora queremos encontrar la distancia más corta agregando un k-ésimo punto intermedio. Existen dos casos: podemos ir de i a k y después a j, o mantener la distancia de i a j que ya teníamos. En ambos estamos considerando los k -1 puntos como intermedios. Al hacer que k tome el valor de todos los vértices, obtenemos la distancia más corta entre todas las parejas.
Visto como formula, donde dk(i,j) es la distancia mínima para ir de i a j con k puntos, y p(i, j) es el peso de la arista de i a j, tenemos que:

Al analizar un grafo G con peso y n vértices, podemos obtener la matriz de peso.
Si 1, 2, 3...,
n
son los vértices, entonces el elemento en la fila
i
y la columna
j
, es
0
si
i=j
. Si no existe arista directa de
i
a
j
, toma el valor de -1. Si de
i
a
j
existe arista directa, entonces toma el valor del peso de la arista. De esta manera se forma la matriz de adyacencias.
De esta manera podremos mejorar las distancias entre cada par de nodos y además obtener la matriz de nodos intermedios.
Pseudocódigo
Floyd-Warshall (G)

Inicializar
D = A ' matriz de distancias = matriz de arcos

si i=j o Dij= infinito entonces Pi,j = nulo sino Pi,j=i 'matriz de caminos

for k = 1 to V
for i = 1 to V
for j = 1 to V
Di,j = min(Di,j , Di,k + Dk,j )
si min = Di,k + Dk,j entonces
Pi,j = Pk,j
fin
Este algoritmo se puede aplicar a multitud de problemas, incluyendo el diseño de circuitos, el diseño de rutas de transporte, aproximaciones al problema del viajante de comercio, o como base de otros algoritmos más complejos.
Complejidad
El algoritmo es capaz de hacer esto con solo V^3 comparaciones. Lo hace mejorando paulatinamente una estimación del camino más corto entre dos vértices, hasta que se sabe que la estimación es óptima.

V*V*V=V^3 por lo tanto la complejidad de este algoritmo es O(V^3).

Donde V es el numero de vértices del grafo.


Ejemplo
Una empresa de transporte desea saber cual es la ruta más económica en sus recorridos entre ciudades donde presta el servicio. Ya que algunas rutas le están generando perdidas por el alto costo de los peajes.
Matriz de costos
Matriz de vértices intermedios
Con k=A, comenzamos a revisar el algoritmo preguntando si:

MatrizdePeso[i][k] + MatrizdePeso[k][j] < MatrizdePeso[i][j], si es menor se cambia, si no se mantiene. Así obtenemos la matriz Mc1 y Mr1.
Realizamos el mismo proceso, pero ahora con k=B
Después del procedimiento anterior, este algoritmo proporciona dos matrices, una de costos mínimos y la otra de recorridos.
Ahora podemos saber cual es el costo mínimo a pagar en peajes de una ciudad a otra, y además podemos saber cual es el recorrido que se debe hacer.
Gracias
Full transcript