Camino
mínimo entre todos los pares de nodos
Robert
W. Floyd nació el 8 de junio de
1936 en Nueva York, es profesor de la Stanford University (B.A. Chicago 1955
B.S. Chicago 1958), y en 1978 fue galardonado con el prestigioso premio A.M.
Turing que otorga la ACM para reconocer las contribuciones de naturaleza técnica
realizadas a la comunidad informática. El premio le fue concedido por tener una
influencia clara en las metodologías para la creación de software eficiente y
fiable, y por ayudar a fundar las siguientes áreas de la informática: teoría de
análisis sintáctico, semántica de los lenguajes de programación, verificación
automática de programas, síntesis automática de programas y análisis de
algoritmos.
Fue uno de los inventores
del deterministic
linear time selection algorithm. También introdujo mejoras en los
algoritmos quicksort y quickselect..
Algoritmo de Floyd-Warshall
(todos los caminos mínimos)
El
problema que intenta resolver este algoritmo es el de encontrar el
camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es
semejante a construir una tabla con todas las distancias mínimas entre pares de
ciudades de un mapa, indicando además la ruta a seguir para ir de la primera
ciudad a la segunda. Este es uno de los problemas más interesantes que se
pueden resolver con algoritmos de grafos.
Existen
varias soluciones a este problema y los algoritmos a aplicar dependen también
de la existencia de arcos con pesos o costes negativos en el grafo. En el caso
de no existir pesos negativos, sería posible ejecutar Vveces el algoritmo
de Dijkstra para el cálculo del camino mínimo, donde V es el número de vértices
o nodos del grafo. Esto conllevaría un tiempo de ejecución de O (V^3) (aunque
se puede reducir). Si existen arcos con pesos negativos, se puede ejecutar
también V veces el Algoritmo de Bellman-Ford, una vez para cada nodo
del grafo. Para grafos densos (con muchas conexiones o arcos) esto conllevaría
un tiempo de ejecución de O (V^4).
Ejemplo:
Grafos
subrayará todos los arcos que formen parte de algún camino mínimo. Los
itinerarios o caminos entre pares de nodos aparecerán descritos en el texto del
análisis. Es importante comprender el significado de la matriz de distancias
mínimas y de la matriz de caminos.
Fuente:
0 comentarios:
Publicar un comentario