Floyd–Warshall algorithm
Algoritmo de Floyd-Warshall
- Date
- 1959-1962 · confidence high
- Place
- Cambridge, Massachusetts, United States
- Credited to
- Robert Floyd and Stephen Warshall, with an earlier contribution by Bernard Roy in 1959
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What it is
An algorithm that computes, in a single run, the shortest distances between every pair of nodes in a directed weighted graph, even with negative weights, as long as there are no negative cycles. It can also compute the transitive closure of a relation.
Bernard Roy had published an equivalent algorithm in 1959, so it is also known as the Roy-Warshall or Roy-Floyd algorithm.
What it led to
- Efficient route computation in transport and telecommunications networks
- Use in the Schulze voting system to compute widest paths