Floyd

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 deestudiantes 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 entretodos 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 estealgoritmo 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 formade 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 hallarla 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 paresde 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 denodos.
• 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 estabaanteriormente, 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...