Algoritmo Floyd Warshall

---

• 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 es 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.

Es decir el algoritmo es el siguiente:

• Iniciación.
  – matriz de distancias.
  – distancia del enlace entre el nodo i y el nodo j.
• Iteración. Para n=0,1 … ,N-1
  
  Empezando con el nodo 1 como intermedio (n=0), se prueba con todos los nodos como nodos intermedios, el último es con el nodo N como nodo intermedio (n=N-1), y así se van hallando las distancias mínimas.

---

Árboles

---

Para el desarrollo de los siguientes conceptos vamos a tomar como ejemplo la siguiente red:

y sobre ella vamos a definir:

• Arbol de expansión (Spanning tree)de una red es un subconjunto de la red en el que conseguimos:
  1. Mantener la conectividad; es posible alcanzar cualquier nodo desde otro.
  2. No hay lazos, no hay bucles topológicos.

  No es único; un ejemplo sobre la red anterior es:

• 
• Se suele usar cuando se desea hacer una inundación, ya que si todos los nodos tienen en su tabla de encaminamiento el mismo árbol de expansión, no se producirán bucles y todos los paquetes llegan a todos los nodos. Se usa sobre todo en difusiones.
• Arbol de expansión de coste o distancia mínima
  Es un árbol de expansión que cumple que el sumatorio de distancias que emplea es mínimo.
  Por ejemplo el anterior tiene coste 10.
  El siguiente es mínimo ( su suma de distancias es 5);no existe otro con suma de distancias menor.
• Arbol divergente de un nodo.
  Hay un árbol divergente por cada nodo sin embargo hay un árbol de expansión para toda la red.
  El árbol divergente de un nodo es aquel árbol que determina las distancias más cortas de ese nodo al resto de los nodos: es, expresada de forma gráfica, la tabla de encaminamiento de cada nodo.
  Por ejemplo, en la red usada como ejemplo, el árbol divergente del nodo A, es el siguiente:
• 

---

---

Para el ejemplo anterior las matrices serían:

---

Nota:El nodo 1 es el nodo A de la red, el 2 es el B y así sucesivamente.
La segunda matriz tiene el nodo 1 como nodo intermedio, la tercera matriz tiene el nodo 2 como nodo intermedio, … y así hasta la última matriz que tiene el nodo 5 como nodo intermedio y da como resultado la matriz de distancias mínimas buscada.

---

• La última matriz es la matriz de distancias buscada, ya que se han probado todos los nodos intermedios.
• El algoritmo da sólo la menor distancia; se debe manejar información adicional para encontrar tablas de encaminamiento.
• Hasta no hallar la última matriz no se encuentran las distancias mínimas.
• Su complejidad es del orden de .

Encontre 2 videos que explican como realizarlo.

y mi ejemplo que realizamos en el salon de clases 😀

a travez de este grafo se usa el mismo metodo …

esto fue un poco dificil aun tengo dudas si lo tengo bien todavia falta corroborar agradeceria comentarios 😀

Referencias

http://ants.dif.um.es/asignaturas/redes/redes/tema3/floyd.htm