Algoritmo De Floyd Warshall
Páginas: 2 (457 palabras)
Publicado: 9 de abril de 2015
Algoritmo de Floyd-Warshall
Que es:
Este algoritmo busca el camino mínimo en un grafo, mediante varias comparaciones hasta lograrlo.
Ejemplo: teniendo el siguiente grafo, se desarrolla elalgoritmo Floyd-Warshall
Se construye dos matrices: de distancias y caminos.
Matriz de distancias (D): que es similar a una matriz de adyacencia de NxN donde N es el orden de grafo, teniendolas distancias que hay entre dos nodos adyacentes. En las posiciones donde i es igual a j se deja en blanco (o guión)
Matriz de caminos (S): es similar a la matriz de distancias, con la diferenciaque se llenan las columnas por los valores de cabecera. En las posiciones donde i es igual a j se deja en blanco (o guión)
En la primera iteración se marca la primera fila y la primeracolumna en la matriz de distancias
En las posiciones restantes de la matriz de distancias se busca mejorar de la siguiente forma: (k cuenta las iteraciones, i y j son los índices de los arreglos)Si (D[i,k]+D[k,j]) < D[i,j]) Y (i<>j) Entonces
D[i,j] = D[i,k]+D[k,j]
Fin_Si
Tomando el elemento D[2,3] que tiene valor ∞, se cambia por 13 que es 3+10 (D[2,1]+D[1,3]), y en la misma posiciónpero de la matriz de caminos se cambia por el valor de la iteración, que en estos momentos es 1
Quedando las matrices en este primer paso, de la primera iteración de la siguiente forma:Completando las posiciones de la primera iteración, las matrices quedan de la siguiente forma:
En la segunda iteración, la fila y la columna se marca
Y mejorando las posiciones resultantescon respecto a la fila y columna marcadas, la matriz queda así:
Continuando con la tercera iteración:
La cuarta iteración:
La quinta y última iteración, que queda de lamisma forma:
De estas dos matrices, se concluye lo siguiente:
En la matriz de distancias, se indica la distancia total que hay entre dos vértices
En la matriz de caminos, se indica el...
Algoritmo de Floyd-Warshall
Que es:
Este algoritmo busca el camino mínimo en un grafo, mediante varias comparaciones hasta lograrlo.
Ejemplo: teniendo el siguiente grafo, se desarrolla elalgoritmo Floyd-Warshall
Se construye dos matrices: de distancias y caminos.
Matriz de distancias (D): que es similar a una matriz de adyacencia de NxN donde N es el orden de grafo, teniendolas distancias que hay entre dos nodos adyacentes. En las posiciones donde i es igual a j se deja en blanco (o guión)
Matriz de caminos (S): es similar a la matriz de distancias, con la diferenciaque se llenan las columnas por los valores de cabecera. En las posiciones donde i es igual a j se deja en blanco (o guión)
En la primera iteración se marca la primera fila y la primeracolumna en la matriz de distancias
En las posiciones restantes de la matriz de distancias se busca mejorar de la siguiente forma: (k cuenta las iteraciones, i y j son los índices de los arreglos)Si (D[i,k]+D[k,j]) < D[i,j]) Y (i<>j) Entonces
D[i,j] = D[i,k]+D[k,j]
Fin_Si
Tomando el elemento D[2,3] que tiene valor ∞, se cambia por 13 que es 3+10 (D[2,1]+D[1,3]), y en la misma posiciónpero de la matriz de caminos se cambia por el valor de la iteración, que en estos momentos es 1
Quedando las matrices en este primer paso, de la primera iteración de la siguiente forma:Completando las posiciones de la primera iteración, las matrices quedan de la siguiente forma:
En la segunda iteración, la fila y la columna se marca
Y mejorando las posiciones resultantescon respecto a la fila y columna marcadas, la matriz queda así:
Continuando con la tercera iteración:
La cuarta iteración:
La quinta y última iteración, que queda de lamisma forma:
De estas dos matrices, se concluye lo siguiente:
En la matriz de distancias, se indica la distancia total que hay entre dos vértices
En la matriz de caminos, se indica el...
Leer documento completo
Regístrate para leer el documento completo.