Ruta más corta entre todo par de nodos
Si se busca la ruta más corta entre todo par de nodos se necesita saber primero los métodos que utilizamos para encontrar la ruta más corta entre dos nodos específicos, pero n veces, ya que vamos a recorrer dos nodos específicos n veces.
En esta ruta, como en la anterior, se aceptan cualquier tipo de costos, ya sean negativos o positivos. Encuentra circuitos negativos.
Encuentra arborescencias de rutas más cortas, así como rutas más cortas entre todo par de nodos.
Es necesario tener una red dirigida, no necesariamente conexa.
Para resolver este tipo de problemas se usa el método de Floyd.
El método de Floyd consta de dos matrices:
-
C: Matriz de nxn , la cual controla los costos de las rutas, es decir, las distancias entre los nodos.
-
Z: Matriz de nxn, en la cual se encuentran los nodos antecesores. Esta matriz es la que nos ayudará a encontrar las rutas entre los nodos.
Ejemplo: Encontrar la ruta más corta entre todo par de nodos por el método de Floyd
Primero se necesita obtener las matrices C y Z
Para k=1 (la primera iteración), buscar en i y en j columnas y renglones sin infinito, respectivamente.
i=2, j=2,3,4
C22=min{0,(3+5)}=0
C23=min{1,(3+5)}=1
C24=min{infinito, (3+2)}=5
Como en C24, se elije un valor menos al establecido en la matriz original C, se actualiza la matriz C y la matriz Z, refiriéndose que en ese lugar existe una ruta más corta entre esos nodos.
Se actualizan las matrices para la segunda iteración.
K= 2
i=1,4 j=1,3,4
C11=min{0,(3+5)}=0
C13=min{5,(5+1)}=5
C14=min{2, (5+5)}=2
C41=min{infinito,(3+4)}=7
C43=min{infinito,(4+1)}=5
C44=min{0, (4+5)}=0
Para k=3
i=1,2,4 j=4
C14=min{2,8}=2
C24=min{5,4}=4
C44=min{0,8}=0
Para k=4
i=1,2,3 j=1,2,3
C11=min{0,9}=0
C12=min{5,6}=5
C13=min{5,7}=5
C21=min{3,11}=3
C22=min{0,8}=8
C23=min{1,9}=1
C31=min{infinito,10}=10
C32=min{infinito,7}=7
C33=min{0,8}=0
Las iteraciones terminan cuando llegas a k=al número de nodos en la red, en este caso, las iteraciones terminaron, quedando las siguientes matrices:
Con ambas matrices, encontrar las rutas y sus costos es más fácil.
Por ejemplo, si queremos buscar la ruta del nodo 3 al nodo 1, podemos ver que en la matriz Z nos indica que el nodo que sigue de 3, será el nodo 4 y el camino del nodo 4 al nodo 1, el nodo que sigue es el 2. Y en la matriz C podremos ver que el costo de esta ruta es de 10. Y podemos observar que eso es cierto si marcamos la ruta.
