In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
, the
Floyd–Warshall algorithm (sometimes known as the
WFI Algorithm or
Roy–Floyd algorithm, since
Bernard RoyBernard Roy , is and emeritus professor at the Université Paris-Dauphine. In 1974 he founded the "Laboratoire d'Analyse et de Modélisation des Systèmes pour l'Aide à la Décision" . He has worked on the graph theory and on multiple criteria decision aiding, having created the ELECTRE methods, stands...
described this algorithm in 1959) is a
graphIn mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
analysis
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
for finding
shortest pathsIn graph theory, the shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized...
in a weighted, directed graph. A single execution of the algorithm will find the shortest paths between
all pairs of vertices. The
Floyd–Warshall algorithm is named after
Robert FloydRobert W Floyd was an eminent computer scientist.Born in New York, Floyd finished school at age 14...
and
Stephen WarshallStephen Warshall was born in New York City. During his career Warshall carried out research and development in operating systems, compiler design, language design, and operations research. Warshall died on December 11, 2006 of cancer at his home in Gloucester, MA. He is survived by his wife, Sarah...
; it is an example of
dynamic programmingIn mathematics and computer science, dynamic programming is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of overlapping subproblems and optimal substructure...
.
The Floyd-Warshall algorithm compares all possible paths through the graph between each pair of vertices.
In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
, the
Floyd–Warshall algorithm (sometimes known as the
WFI Algorithm or
Roy–Floyd algorithm, since
Bernard RoyBernard Roy , is and emeritus professor at the Université Paris-Dauphine. In 1974 he founded the "Laboratoire d'Analyse et de Modélisation des Systèmes pour l'Aide à la Décision" . He has worked on the graph theory and on multiple criteria decision aiding, having created the ELECTRE methods, stands...
described this algorithm in 1959) is a
graphIn mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
analysis
algorithmIn mathematics, computing, linguistics, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields....
for finding
shortest pathsIn graph theory, the shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized...
in a weighted, directed graph. A single execution of the algorithm will find the shortest paths between
all pairs of vertices. The
Floyd–Warshall algorithm is named after
Robert FloydRobert W Floyd was an eminent computer scientist.Born in New York, Floyd finished school at age 14...
and
Stephen WarshallStephen Warshall was born in New York City. During his career Warshall carried out research and development in operating systems, compiler design, language design, and operations research. Warshall died on December 11, 2006 of cancer at his home in Gloucester, MA. He is survived by his wife, Sarah...
; it is an example of
dynamic programmingIn mathematics and computer science, dynamic programming is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of overlapping subproblems and optimal substructure...
.
Algorithm
The Floyd-Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with only comparisons. This is remarkable considering that there may be up to edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is known to be optimal.
Consider a graph with vertices , each numbered 1 through N. Further consider a function that returns the shortest possible path from to using only vertices 1 through as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each to each using only nodes 1 through .
There are two candidates for this path: either the true shortest path only uses nodes in the set ; or there exists some path that goes from to , then from to that is better. We know that the best path from to that only uses nodes 1 through is defined by , and it is clear that if there were a better path from to to , then the length of this path would be the concatenation of the shortest path from to (using vertices in ) and the shortest path from to (also using vertices in ).
Therefore, we can define in terms of the following
recursiveRecursive may refer to:*Recursion*Recursively enumerable language*Recursively enumerable set*Recursive filter*Recursive function*Recursive language*Recursive acronym*Recursive set*Primitive recursive function...
formula:
This formula is the heart of Floyd-Warshall. The algorithm works by first computing for all (i,j) pairs, then using that to find for all pairs, etc. This process continues until k=n, and we have found the shortest path for all pairs using any intermediate vertices.
Pseudocode
Conveniently, when calculating the th case, one can overwrite the information saved from the computation of . This means the algorithm uses quadratic memory. Be careful to note the initialization conditions:
1 /* Assume a function
edgeCost(i,j) which returns the cost of the edge from i to j
2 (infinity if there is none).
3 Also assume that
n is the number of vertices and
edgeCost(i,i)=0
4 */
5
6
int path[][];
7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
8 from i to j using intermediate vertices (1..k-1). Each path[i][j] is initialized to
9
edgeCost(i,j) or infinity if there is no edge between
i and
j.
10 */
11
12
procedure FloydWarshall
13
for to
14
for each in
15 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
Behaviour with negative cycles
For numerically meaningful output, Floyd-Warshall assumes that there are no negative cycles (in fact, between any pair of vertices which form part of a negative cycle, the shortest path is not well-defined because the path can be arbitrarily negative). Nevertheless, if there are negative cycles, Floyd–Warshall can be used to detect them. The intuition is as follows:
- The Floyd-Walshall algorithm iteratively revises path lengths between all pairs of verticies , including where ;
- Initially, the length of the path is zero;
- A path can only improve upon this if it has length less than zero, i.e. denotes a negative cycle;
- Thus, after the algorithm, will be negative if there exists a negative-length path from back to .
Hence, to detect negative cycles using the Floyd-Walshall, one can inspect the diagonal of the path matrix, and the presence of a negative number indicates that the graph contains at least one negative cycle.
Analysis
To find all of from those of requires bit operations. Since we begin with and compute the sequence of zero-one matrices , , , , the total number of bit operations used is . Therefore, the
complexityComputational complexity theory is a branch of the theory of computation in computer science that focuses on classifying computational problems according to their inherent difficulty. In this context, a computational problem is understood to be a task that is in principle amenable to being solved...
of the algorithm is and can be solved by a deterministic machine in
polynomial timeIn computer science, polynomial time refers to the running time of an algorithm, that is, the number of computation steps a computer or an abstract machine requires to evaluate the algorithm....
.
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
In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R....
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 conjunctionIn logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
(AND) and the minimum operation by logical disjunctionIn logic and mathematics, or, also known as logical disjunction or inclusive disjunction, is a logical operator that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are true. In grammar, or is a...
(OR).
- Finding a regular expression
In computing, regular expressions provide a concise and flexible means for identifying strings of text of interest, such as particular characters, words, or patterns of characters...
denoting the regular languageIn theoretical computer science, a regular language is a formal language that satisfies the following equivalent properties:...
accepted by a finite automaton (Kleene's algorithm)
- Inversion
In linear algebra, an n-by-n matrix A is called invertible or nonsingular or nondegenerate if there exists an n-by-n matrix B such that...
of realIn mathematics, the real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339..., where the digits continue in some way; or, the real...
matricesIn mathematics, a matrix is a rectangular array of numbers, such asEntries of a matrix are often denoted by a variable with two subscripts, as shown on the right. Matrices of the same size can be added and subtracted entrywise and matrices of compatible size can be multiplied...
(Gauss-Jordan algorithm).
- 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.
- Testing whether an undirected graph is bipartite
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
.
- Fast computation of Pathfinder Networks
Several Psychometric scaling methods start from proximity data and yield structures revealing the underlying organization of the data. Data clustering and multidimensional scaling are two such methods. Network scaling represents another method based on graph theory. Pathfinder networks are...
.
- Maximum Bandwidth Paths in Flow Networks
Implementations
- A Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall, a linguist working as a systems administrator for NASA, in 1987, as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone...
implementation is available in the Graph module
- A Javascript
JavaScript is an object-oriented scripting language used to enable programmatic access to objects within both the client application and other applications. It is primarily used in the form of client-side JavaScript, implemented as an integrated component of the web browser, allowing the...
implementation is available at Alex Le's Blog
- A Python
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
implementation is available in the NetworkX package
- A C
C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
implementation is available at joshuarobinson.net
- A C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
implementation is available in the boost::graph library
- A Java
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
implementation is in the Apache commons graph library.
- Another Java implementation is on Algowiki
- A C#
C-sharp may refer to:* C♯ * Musical scales:** C-sharp major** C-sharp minor* C#...
implementation is in QuickGraph
- A PHP
PHP, or PHP: Hypertext Preprocessor, is a widely used, general-purpose scripting language that was originally designed for web development, to produce dynamic web pages. It can be embedded into HTML and generally runs on a web server, which needs to be configured to process PHP code and create web...
implementation and PL/pgSQLPL/pgSQL is a procedural language supported by the PostgreSQL RDBMS. It closely resembles Oracle's PL/SQL language....
implementation are available at Microshell.
- A MATLAB
MATLAB is a numerical computing environment and fourth generation programming language. Developed by The MathWorks, MATLAB allows matrix manipulation, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs in other languages...
implementation is available using the Matlab_bgl package.
See also
- Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing. An equivalent...
, an algorithm for finding single-source shortest paths in a more restrictive class of inputs, graphs in which all edge weights are non-negative
- Johnson's algorithm
Johnson's algorithm is a way to find shortest paths between all pairs of vertices in a sparse directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist...
, an algorithm for solving the same problem as the Floyd–Warshall algorithm, all pairs shortest paths in graphs with some edge weights negative. Compared to the Floyd–Warshall algorithm, Johnson's algorithm is more efficient for sparse graphs.
External links