Algoritmo de Floyd-Warshall
Floyd–Warshall algorithm
- Fecha
- 1959-1962 · fiabilidad alta
- Lugar
- Cambridge, Massachusetts, EE. UU.
- Autoría
- Robert Floyd y Stephen Warshall, con un antecedente de Bernard Roy en 1959
- Ámbito
- Saber y símbolos
⚠️ Dato en discusión: las fuentes no coinciden.
Qué es
Algoritmo que calcula en una sola ejecución las distancias más cortas entre todos los pares de nodos de un grafo dirigido con pesos, incluso negativos, siempre que no haya ciclos negativos. También sirve para calcular el cierre transitivo de una relación.
Bernard Roy había publicado un algoritmo equivalente en 1959, por lo que también se le conoce como algoritmo de Roy-Warshall o Roy-Floyd.
A qué dio paso
- Cálculo eficiente de rutas en redes de transporte y telecomunicaciones
- Uso en el sistema de votación de Schulze para calcular caminos más anchos