Algoritmo De Floyd

Algoritmo de Floyd-Warshall.




Ejemplo:

Veamos un ejemplo de cómo trabaja el algoritmo:
Sea el grafo:

[pic]












La matriz D0 se llena con los pesos de cadacamino 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, porlo 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 nodosque 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 losdemá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.






































































-----------------------
8

2

49

1

1

2

3

4



1

9

2

(

4

1

(

(

(

(

1

(

8

3

2

1

4

3

2

1

Matriz de Peso

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

9

2

(

4

1

(

(

(

(

1

(

8

3

2

1

4

3


(

Matriz NodosIntermedios

D0

4

3

2

1

1

3

2

4

4

1

4

3

2

3

2

1

4

3

2

1

S0

4

2

1

D0

4

3

2

1

1

3

2

4

4

1

4...