Algoritmo de Warshall (cierre transitivo) - SergioRiosC/Datos-1 GitHub Wiki

• Permite determinar si hay camino entre nodos de un grafo
• Calcula la matriz de caminos de un grafo G de n vertices representado por la matriz de adyacencia A
• Define una secuencia de matrices Pk[i,j] tienen un cero si no hay camino, o 1 si hay camino de Vi, Vj o traves de Vk
• Asi sucesivamente hasta llegar a ps

Algoritmo de camino mas corto para todos los vertices

• Se podria aplicar Dijkstra para todos los vertices pero seria ineficiente
• El algoritmo Floyd-Warshall es mas directo para calcular las rutas optimas para todos los vertices
• El grafo se representa con la matriz de pesos. Si no hay arco/arista, se considera infinito
• La diagonal es infinito
• Al igual que Warshall genera una matriz de nxn. En cada paso, se incorpora un nuevo vertice y se evaluan las rutas
• De igual forma, se generan n matrices predecesores
  W0{Cij peso del arco Vi a Vj inf si no hay arco
  W1[i,j]=minimo(D0[i,j],D0[i,1]+D0[1,j])
  Wk[i,j]=min(Dk-1[i,j],Dk-1[i,k],Dk-1[k,j])