Algoritmo de Floyd

El algoritmo de Floyd - Warshal fue creado por el informático Robert W. Floyd en 1962, como necesidad de encontrar el camino más corto entre los nodos o vértices de un grafo, similar a construir una tabla con las distancias mínimas entre varias ciudades en un mapa, además indicando la ruta a seguir para pasar de una a otra.

Como ejemplo, se utilizara el siguiente grafo:

1) Ahora, se deberán construir las siguientes tablas:

Para la tabla ponderaciones, se marca el camino principal (-), luego, los valores para cada vértice, en caso de que un vértice no cuente con valor (como lo es de D al C, basta con colocar el símbolo infinito ∞.

La tabla recorrido, se llenara con la variable de cada columna, tal como se muestra en la imagen anterior.

2) Teniendo en cuenta las variables principales (A, B, C, D) se procede con la siguiente validación.

Tomando el primer nodo A, se identifica tanto la fila como la columna que le corresponde:

Verificamos que el la suma de los valores de BA y AB sea mayor a BB, si cumple esta condición, se deja el valor de BB sin cambios, de ser menor, se procede a cambiar su valor por la sumatoria resultante:

Cumple la condición

Cumple la condicion

Cumple la condición

Cumplen la condición

No cumple la condicíón

En el caso anterior, la suma entre DB y AB es igual a 11, teniendo en cuenta que el valor de DB es infinito, no se cumple la condición de que la sumatoria sea mayor, por lo que se reemplaza el valor de DB por 11, y en la tabla recorrido cambiamos el valor de DB por A, ya que es el nodo sobre el cual se está realizando el proceso, resultando:

Se continúa con la validación teniendo como base el nodo A:

No cumple la condicion

Como no cumple la condición, se cambia el valor de DC en la tabla ponderaciones por el resultado de la suma (12), así como en la tabla recorrido se cambia el valor de DC por A:

Continuando con el recorrido:

Cumple la condición

3) Una vez finalizada la validación teniendo como base el nodo Ha, se procede a realizar el mismo procedimiento para B, C y D, teniendo en cuenta las observaciones anteriormente dadas.

En caso de que al finalizar la validación para A, B, C y D, y aun aparezca en la tabla ponderaciones valores infinitos, iniciamos de nuevo la validación, hasta que no aparezcan los símbolos negativos, resultando en este caso para las tablas ponderaciones y recorrido:

4) Una vez se tienen las tablas ponderaciones y recorrido, se procede a verificar los caminos más cortos para llegar de un nodo a otro.

Por ejemplo (tomando como guía la tabla recorrido), si quiero llegar del nodo A al nodo D, se indica que el recorrido más corto es pasar por el nodo C,  el cual consta de un valor de recorrido 7 (en base a la tabla ponderaciones).

Código C++: