Editing Floyd–Warshall algorithm (section)

==Applications and generalizations==
The Floyd–Warshall algorithm can be used to solve the following problems, among others:
* Shortest paths in directed graphs (Floyd's algorithm).
* [[Transitive closure]] of directed graphs (Warshall's algorithm). In Warshall's original formulation of the algorithm, the graph is unweighted and represented by a Boolean [[adjacency matrix]]. Then the addition operation is replaced by [[logical conjunction]] (AND) and the minimum operation by [[logical disjunction]] (OR).
* Finding a [[regular expression]] denoting the [[regular language]] accepted by a [[finite automaton]] ([[Kleene's algorithm]], a closely related generalization of the Floyd–Warshall algorithm)<ref>{{citation|title=Handbook of Graph Theory|series=Discrete Mathematics and Its Applications|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press|year=2003|page=65|url=https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65|isbn=9780203490204}}.</ref>
* [[invertible matrix|Inversion]] of [[real number|real]] [[matrix (mathematics)|matrices]] ([[Gauss–Jordan elimination|Gauss–Jordan algorithm]])<ref>{{cite web | archive-url = https://web.archive.org/web/20091022202353/http://geocities.com/rpenalozan/ps/graphalg2005.ps | archive-date = 2009-10-22|url-status=dead | url = http://geocities.com/rpenalozan/ps/graphalg2005.ps | title = Algebraic Structures for Transitive Closure | first = Rafael | last = Peñaloza | publisher = Dresden University of Technology, Department of Computer Science, Institute for Theoretical Computer Science|work = Seminar "Graph Algorithms"}}</ref>
* Optimal routing. In this application one is interested in finding the path with the maximum flow between two vertices. This means that, rather than taking minima as in the pseudocode above, one instead takes maxima. The edge weights represent fixed constraints on flow. Path weights represent bottlenecks; so the addition operation above is replaced by the minimum operation.
* Fast computation of [[Pathfinder network]]s.
* [[Widest path problem|Widest paths/Maximum bandwidth paths]]
* Computing canonical form of difference bound matrices (DBMs)
* Computing the similarity between graphs
* Transitive closure in AND/OR/threshold graphs.<ref>{{cite report | title=Scheduling Tasks with AND/OR precedence contraints (PhD Thesis, Appendix B)| first=Donald| last=Gillies|year=1993|url=http://www.ece.ubc.ca/~gillies/download/Donald_W_Gillies_PhD_1993_Scheduling_With_AND_OR_Precedence.pdf}}</ref>