Participacion 2.6

Método de Floyd

a) Ruta más corta ¿Qué problemática tiene el problema? Ubica al menos una ruta

Primero establecemos las matrices Cij y Zij:

Ahora realizamos el algoritmo:
para k=1 no hay valores para "i", asi que pasamos al siguiente

k=2
i=1, 3      j= 4, 5
C14=min{infinito,3+4}=7    Z14=Z24
C15=min{infinito,3+1}=4    Z15=Z25
C34=min{infinito,2+4}=6    Z34=Z34
C35=min{infinito,2+1}=3    Z35=Z35

k=3
i= 1,4     j=2,4,5
C12=min{3,-2+2}=0          Z12=Z32
C14=min{7,-2+6}=4          Z14=Z34
C15=min{4,-2+3}=1          Z15=Z35
C42=min{infinito,3+2}=5    Z42=Z32
C44=min{0,3+6}=---        
C45=min{}0,3+3=---         

z=4
i=1,2,3   j=2,3
C12=min{0,4+5}=---
C13=min{-2,4+3}=---
C22=min{0,4+5}=---
C23=min{7,4+3}=---
C32=min{2,6+5}=---
C33=min{0,6+3}=--- 

para k=5 no hay valores para "i", asi que ya tenemos nuestras matrices:

El problema que se puede observar, es que quedaron algunos simbolos de infinito, lo cual nos indica que hay rutas entre dos nodos especificos de las cuales no nos dira su costo.