Algoritmo De Floyd

Universidad Nacional Autónoma de México Facultad de Ingeniería Algoritmos y Estructuras de Datos Trabajo: Algoritmo de Floyd Arrieta Peralta José Carlos 2012-1

Introducción
Por principio se podría decir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio, es decir, un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneasque une cada par de vértices. Por otro lado, debido a su generalidad y a la gran diversidad de formas que pueden usarse, resulta complejo tratar con todas las ideas relacionadas con un grafo. Para facilitar el estudio de este tipo de dato, a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación, describiéndose en este trabajo elalgoritmo de Floyd-Warshall que compara todos los posibles caminos a través del grafo entre cada par de vértices así encontrando la distancia más corta entre dos puntos. En lugar de buscar los caminos mínimos de un vértice a los demás nos podemos plantear buscar el camino más corto entre cualquier pareja de vértices, es decir, dado un grafo dirigido etiquetado G = {V, A} en el que las etiquetas son nonegativas encontrar el camino de longitud " más corta entre dos vértices cualesquiera de ese grafo. Podría pensarse, para resolver el problema, en aplicar el algoritmo de Dijkstra n veces, una por vértice, pero en lugar de eso, aplicaremos un nuevo algoritmo creado por Floyd que va encontrando los caminos de forma iterativa. Cómo funciona el algoritmo Para este algoritmo tenemos la siguientenotación: V = {1, ..., n} conjunto de vértices. A es una matriz de tamaño n x n en la que se calculará en cada Aij la longitud más corta del camino que va de i a j. P es una matriz de tamaño n x n que utilizaremos para recuperar los caminos más cortos. C es una matriz de dimensión n x n conteniendo los costos de los arcos. Si no existe arco de un vértice i a otro j el correspondiente valor C [i,j] = .Inicialmente A [i,j] = { C[i,j] si i j, 0 si i = j }.

A continuación se itera sobre A n veces de forma que tras hacer la k iteración A[i,j] tiene un valor correspondiente a la longitud más pequeña de cualquier camino de i a j que no pase por un vértice de índice mayor que k, es decir, cualquier vértice

intermedio entre i y j (extremos del camino) ha de ser menor o igual que k. Por tanto encada iteración k se usará la siguiente fórmula:

Ak [i,j] = min(Ak-1 [i,j] ,Ak-1 [i,k] +Ak-1l [k,j])3 es decir, cada Ak [i,j] se obtiene comparando Ak-1 [i,j], el coste de ir de i a j sin pasar por k o cualquier vértice de índice mayor, con A k1 [i,k] +Ak-1 [k,j], el costo de ir primero de i a k y después de k a j sin pasar por un vértice de índice mayor que k de forma que si el paso por elvértice k produce un camino i más corto que el indicado por Ak-1 [i,j], se elige ese coste para Ak [i,j] .Así mismo, cada iteración P [i,j] contendrá el vértice k que permitió al algoritmo de Floyd encontrar el valor más pequeño de A[i, j] .Inicialmente P[i,j] = 0, puesto que inicialmente el camino más corto de i a j es el propio arco. El algoritmo sería el siguiente: Algoritmo Floyd()

1. for (i = 1;i 0 con la que el camino es (2,3,1,4) con costo 12. Análisis(propias palabras): Para fabricar la matriz A del distancia tenemos que ver las conexiones y caminos para llegar a los vértices se pone el peso de la arista y así se va fabricando la matriz si un nodo esta direccionado solo puede haber dato en la dirección que marque e la flecha y al contrario de la dirección se le pone ∞ y de igualmanera en vértices que no estén conectados. Para la matriz P que es de recorrido se va llenando según la iteración que valla y si en dicha iteración se modifican el valor de algún dato ya sean datos dados o los ∞. Para empezar a llenar la matriz de distancia tendremos hacer iteraciones en la primera se tachan la fila 1 y la columna 1 las casillas que quedan libres se van modificando solo si las...