El algoritmo de floyd y warshall

clindy · 01/03/2011, 12:23

AUTORES:
Ricardo Alberto Vargas Esquerre
Carlos Manuel Zarate Florián
Claudia María Valdivieso Castillo
Gerson Eddy Rodríguez Rodríguez

RESUMEN: Este trabajo ha sido elaborado por un grupo de estudiantes de la Universidad Nacional de Trujillo con el fin de explicar de la manera más detallada posible el algoritmo de Floyd y Warshall, el cual soluciona el problema de buscar el camino más corto entre todos los pares de nodos o vértices de un grafo .La gracia del algoritmo de Floyd y Warshall radica en que trabaja con programación dinámica, lo que garantiza que la solución entregada por este algoritmo sea optima.

Esperamos que este trabajo sea de gran ayuda para quienes hagan uso de este.

INTRODUCCION

Muchos problemas de la vida cotidiana se pueden expresar e incluso resolver en forma de grafo. Existen algoritmos que encuentran distintos tipos de soluciones, tanto booleanas como de eficiencia. El grafo se representa en una tabla (matriz, arreglo; para los lenguajes de programación) que se conoce como “matriz de adyacencia” y representa si existe una unión entre dos nodos (boolean), o el “peso” entre dos nodos (grafo ponderado).

El algoritmo de Floyd y Warshall, permite hallar la ruta más corta en grafos dirigidos ponderados. El algoritmo de Floyd y Warshall, a diferencia del algoritmo de Dijkstra, no halla las distancias más cortas de un vértice fijo, sino todos los pares de distancias más cortas.

CARACTERÍSTICAS GENERALES

Obtiene la mejor ruta entre todo par de nodos.
Trabaja con la matriz D inicializada con las distancias directas entre todo par de nodos.
La iteración se produce sobre nodos intermedios, es decir, para todo elemento de la matriz se prueba si lo mejor para ir de i a j a través de un nodo intermedio elegido o como estaba anteriormente, y esto se prueba con todos los nodos de la red.
Una vez probados todos los nodos de la red como nodos intermedios, la matriz resultante da la mejor distancia entre todo par de nodos.
Matriz Sn que entrega el nodo intermedio para llegar desde un nodo i a un nodo j del grafo.

PSEUDOCODIGO

Entrada: Grafo dirigido/no dirigido, con peso asociado a las aristas.
Salida:

Matriz Dn que entrega el menor camino para ir de un nodo i a un nodo j del grafo.
Matriz Sn que entrega el nodo intermedio para llegar desde un nodo i a un nodo j del grafo.

El enlace o el Codigo del Programa esta OCULTO o BLOQUEADO Haga click en los anuncios de la ventana para desbloquear el contenido oculto
Click on the ads in the window to unlock hidden content--->
No sabes COMO DESCARGAR? Ve el siguiente VIDEO
Do not know how to download? See the following VIDEO

.

FUNCIONAMIENTO

Como sabemos, en el computador no se puede representar el infinito, por lo tanto, cuando no existía conexión entre dos nodos, inicialicé ese peso con 100000, sabiendo que éste no es número tan grande si es que queremos representar pesos elevados, pero como el desarrollo de esta aplicación fue pensada con fines pedagógicos y no profesionales, en ese caso no importaba mucho.

Veamos un ejemplo de cómo trabaja el algoritmo:

Sea el grafo:

Como vemos acá, el algoritmo no permite que existan nodos que apunten a sí mismos, ya que las diagonales quedan inhabilitadas.

La matriz D0 se llena con los pesos de cada camino que representa la matriz[i][j] del ejemplo, como vemos, si no existe conexión entre los nodos, se completa con el símbolo lo que reprenda que no existe la conexión entre los nodos, por lo tanto el peso que trae pasar por ahí no se puede tasar.

La matriz S0 se llena con los nodos intermedios entre un par de nodos, en este caso suponemos que no existe otro camino entre los nodos que ir directamente hacia ellos.

Luego de completar las primeras matrices, comenzamos fijando una fila y una columna pivote, para ver todos los caminos que existen entre el nodok y todos los demás, cualquier cambio que ocurra el la matriz de peso, incurrirá en un cambio en la matriz de nodos intermedios, asumiendo que localmente el nodok es el de menor peso en esa iteración.

Fijamos la fila 1, entonces k=1, y 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 D1 y S1.

Como se puede ver en las posiciones 3,2 y 3,5 de la matriz de peso, hubo cambios y como habíamos fijado k =1, entonces en las mismas posiciones se generarán cambios en la matriz de nodos intermedios. Ahora fijamos k =2 y seguimos con el procedimiento hasta llegar a k =4, que es el número total de nodos en el grafo.

Como vemos en las posiciones 1,3 y 4,3 de la matriz de peso, hubo cambios y como habíamos fijado k =2, entonces en las mismas posiciones se generarán cambios en la matriz de nodos intermedios. Ahora fijamos k =3 y seguimos con el procedimiento hasta llegar a k =4, que es el número total de nodos en el grafo.

Como vemos en las posiciones 2,1; 2,4 y 4,1 de la matriz de peso, hubo cambios y como habíamos fijado k =3, entonces en las mismas posiciones se generarán cambios en la matriz de nodos intermedios. Ahora fijamos k =4 y seguimos con el procedimiento hasta llegar a k =4, que es el número total de nodos en el grafo.

Como vemos en las posiciones 1,2; 1,3 y 3,2 de la matriz de peso, hubo cambios y como habíamos fijado k =4, entonces en las mismas posiciones se generarán cambios en la matriz de nodos intermedios, y como ya completamos las 4 iteraciones, estas son las matrices con los pesos óptimos y sus respectivos caminos.

CORRECTITUD

INICIALIZACION: Antes de la primera iteración en k=1, i=1,j=1. MATRIZDEPESO (k) es la matriz de pesos que entrega el menor camino entre un par de nodos.

MANTENIMIENTO: Verificar antes de cada iteración en k.

MATRIZDEPESO (k) es la matriz de pesos que entrega el menor camino entre un par de nodos a comparación de MATRIZDEPESOS (k-1).
Donde de cada iteración en k:
MATRIZDEPESOS(k)[i][j]≤MATRIZDEPESOS(k-1)[i][j]

TERMINACION: Al terminar k=n+1.

MATRIZDEPESOS(n) es la matriz de pesos que entrega el menor camino entre un par de nodos.

ANALISIS DE COMPLEJIDAD

Se deben construir n matrices de tamaño non y cada elemento se halla en tiempo constante. Por tanto, la complejidad del algoritmo es O(n3).

El algoritmo de Floyd y Warshall es mucho mas eficiente desde el punto de vista de almacenamiento dado que puede ser implementado una vez actualizado la distancia de la matriz con cada elección en k. En muchas aplicaciones especificas, es más rápido que cualquier versión del algoritmo de Dijkstra.

APLICACIONES Y GENERALIZACIONES

El algoritmo de Floyd y Warshall puede ser utilizado para resolver los siguientes problemas, entre otros:

Camino mínimo en grafos dirigidos (algoritmo de Floyd).
Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo de Warshall. El grafo es un grafo no ponderado y representado por una matriz booleana de adyacencia. Entonces la operación de adición es reemplazada por la conjunción lógica (AND) y operación menor por la disyunción lógica (OR).
Encontrar una expresión regular dada por un lenguaje regular aceptado por un autómata finito (algoritmo de Kleene).
Inversión de matrices de números reales (algoritmo de Gauss - Jordan).
Ruta optima. En esta aplicación es interesante encontrar el camino del flujo máximo entre 2 vértices. Esto significa que en lugar de tomar los mínimos con el pseudocódigo anterior, se coge el máximo. Los pesos de las aristas representan las limitaciones del flujo. Los pesos de los caminos representan cuellos de botella; por ello, la operación de adición anterior es reemplazada por la operación mínimo.
Comprobar si un grafo no dirigido es bipartito.

CONCLUSIONES

El algoritmo de Floyd y Warshall es mucho más eficiente desde el punto de vista de almacenamiento dado que puede ser implementado una vez actualizado la distancia de la matriz con cada elección en k. En muchas aplicaciones especificas, es más rápido que cualquier versión del algoritmo de Dijkstra.

En el siguiente enlace podrán encontrar un ejemplo con un pequeña aplicación realizada en C++ click aqui

REFERENCIAS