Investigacion de operaciones

Algoritmo de Floyd
Sirve para hallar las m´ ınimas distancias entre todos los v´rtices de un grafo valorado e (G, f ), con G = (V, E), de n v´rtices V = {v1 , v2 , ..., vn } con valores positivos,es decir e f : E −→ R+ . Formalmente, la entrada del algoritmo es la matriz de adyacencia n × n M = (aij ), que en cada entrada aij guarda el valor de la flecha vi → vj ∈ E. El algoritmo utiliza comorecurso una matriz del mismo tama˜ o que la matriz de adyacencia, la matriz de n resultados parciales D = (dij ). Al inicio, la matriz de resultados parciales toma el valor de la matriz de adyacencia,es decir, dij = aij . El cuerpo del algoritmo es un bucle indexado por k, tal que en la iteraci´n k-´sima se compara la suma (componente a componente) o e e a de la fila y columna k-´simas de la matrizde resultados parciales, qued´ndose con el m´ ınimo. El resultado del algoritmo, al final del bucle, es la matriz de resultados parciales, que coincidir´ con la matriz de m´ a ınimas distancias. Enpseudoc´digo, representando la entrada dij de la matriz de resultados parciales o D por D[i, j], se tiene: Para k = 0 hasta n hacer { Para i = 0 hasta n hacer { Para j = 0 hasta n hacer { D[i,j] =m´nimo(D[i,j],D[i,k] + D[k,j]) ı } } } [Referencia: http://es.wikipedia.org/wiki/Algoritmo de Floyd-Warshall]

La validez del algoritmo se demuestra teniendo en cuenta el significado de la entrada dij dela matriz de resultados parciales al final de la iteraci´n k-´sima: es el valor del o e camino entre vi y vj , que sea m´ ınimo entre los que pueden opcionalmente utilizar, como v´rtices intermedios,los del conjunto {v1 , v2 , ..., vk }. Es decir dij = m´ (C)), siendo C e ın(f del conjunto de caminos entre vi y vj que utiliza, como mucho, los k primeros v´rtices. e Que se cumple esta propiedad esf´cil de ver en la primera iteraci´n (k = 1), porque a o el valor ai1 + a1j que resulta de sumar la primera fila y la primera columna de la matriz de resultados parciales (que al inicio coincide con...