Algoritmo de Floyd:
En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo
en grafos dirigidos ponderados. El algoritmo encuentra el camino entre
todos los pares de vértices en una única ejecución. El algoritmo de
Floyd-Warshall es un ejemplo de programación dinámica.
Aplicaciones:
El algoritmo de Floyd-Warshall puede ser utilizado para resolver los siguientes problemas, entre otros:- Camino mínimo en grafos dirigidos (algoritmo de Floyd).
- Cierre transitivo en grafos dirigidos (algoritmo de Warshall). Es la formulación original del algoritmo de Warshall. El grafo es un grafo no ponderado y representado por una matriz booleana de adyacencia. Entonces la operación de adición es reemplazada por la conjunción lógica(AND) y la operación menor por la disyunción lógica (OR).
- Encontrar una expresión regular dada por un lenguaje regular aceptado por un autómata finito (algoritmo de Kleene).
- Inversión de matrices de números reales (algoritmo de Gauss-Jordan).
- Ruta optima. En esta aplicación es interesante encontrar el camino del flujo máximo entre 2 vértices. Esto significa que en lugar de tomar los mínimos con el pseudocodigo anterior, se coge el máximo. Los pesos de las aristas representan las limitaciones del flujo. Los pesos de los caminos representan cuellos de botella; por ello, la operación de adición anterior es reemplazada por la operación mínimo.
- Comprobar si un grafo no dirigido es bipartito.
Ejemplo:
Hallar el camino mínimo desde el vértice 3 hasta 4 en el grafo con la siguiente matriz de distancias:Aplicamos el algoritmo de Floyd-Warshall, y para ello en cada iteración fijamos un vértice intermedio.
1ª Iteración: nodo intermedio = 1
La matriz es simétrica, por lo que solamente hará falta calcular el triángulo superior de las distancias.
d23 = min(d23, d21 + d13) = 8
d24 = min(d24, d21 + d14) = 4
d25 = min(d25, d21 + d15) = 9
d26 = min(d26, d21 + d16) =
d32 = min(d32, d31 + d12) = 8
d34 = min(d34, d31 + d14) = 6
d35 = min(d35, d31 + d15) = 7
d36 = min(d36, d31 + d16) = 1
d45 = min(d45, d41 + d15) =
d46 = min(d46, d41 + d16) = 4
d56 = min(d56, d51 + d16) =
La matriz de distancia después de esta iteración es:
d13 = min(d13, d12 + d23) = 5
d14 = min(d14, d12 + d24) = 1
d15 = min(d15, d12 + d25) = 12
d16 = min(d16, d12 + d26) =
d34 = min(d34, d32 + d24) = 6
d35 = min(d35, d32 + d25) = 7
d36 = min(d36, d32 + d26) = 1
d45 = min(d45, d42 + d25) = 13
d46 = min(d46, d42 + d26) = 4
d56 = min(d56, d52 + d26) =
La matriz de distancia después de esta iteración es:
d12 = min(d12, d13 + d32) = 3
d14 = min(d14, d13 + d34) = 1
d15 = min(d15, d13 + d35) = 12
d16 = min(d16, d13 + d36) = 6
d24 = min(d24, d23 + d34) = 4
d25 = min(d25, d23 + d35) = 9
d26 = min(d26, d23 + d36) = 9
d45 = min(d45, d43 + d35) = 13
d46 = min(d46, d43 + d36) = 4
d56 = min(d56, d53 + d36) = 8
La matriz de distancia después de esta iteración es:
d12 = min(d12, d14 + d42) = 3
d13 = min(d13, d14 + d43) = 5
d15 = min(d15, d14 + d45) = 12
d16 = min(d16, d14 + d46) = 5
d23 = min(d23, d24 + d43) = 8
d25 = min(d25, d24 + d45) = 9
d26 = min(d26, d24 + d46) = 8
d35 = min(d35, d34 + d45) = 7
d36 = min(d36, d34 + d46) = 1
d56 = min(d56, d54 + d46) = 8
La matriz de distancia después de esta iteración es:
d12 = min(d12, d15 + d52) = 3
d13 = min(d13, d15 + d53) = 5
d14 = min(d14, d15 + d54) = 1
d16 = min(d16, d15 + d56) = 5
d23 = min(d23, d25 + d53) = 8
d24 = min(d24, d25 + d54) = 4
d26 = min(d26, d25 + d56) = 8
d34 = min(d34, d35 + d54) = 6
d36 = min(d36, d35 + d56) = 1
d46 = min(d46, d45 + d56) = 4
La matriz de distancia después de esta iteración es:
d12 = min(d12, d16 + d62) = 3
d13 = min(d13, d16 + d63) = 5
d14 = min(d14, d16 + d64) = 1
d15 = min(d15, d16 + d65) = 12
d23 = min(d23, d26 + d63) = 8
d24 = min(d24, d26 + d64) = 4
d25 = min(d25, d26 + d65) = 9
d34 = min(d34, d36 + d64) = 5
d35 = min(d35, d36 + d65) = 7
d45 = min(d45, d46 + d65) = 12
La matriz de distancia después de esta iteración es:
Baccarat (Rules & Regulations - The Worrione
ResponderEliminarBaccarat is 샌즈카지노 a great game to learn and understand. It worrione is played without the risk of being cheated, choegocasino but if you want to learn the game, try it now!
The Best Casino Games in 2021 - JTM Hub
ResponderEliminarFrom blackjack to roulette, there's 포항 출장안마 no 이천 출장마사지 shortage 울산광역 출장마사지 of exciting casino games to play. From 서귀포 출장마사지 poker to slots, there's never 통영 출장샵 a dull moment at JTM