Floyd–Warshall algorithm - Revision history

162.158.62.235: Undo revision 2242 by 108.162.219.188 (talk)

2022-04-25T12:16:38Z

Undo revision 2242 by 108.162.219.188 (talk)

108.162.219.188 at 12:12, 25 April 2022

2022-04-25T12:12:18Z

Brian at 05:45, 31 May 2011

2011-05-31T05:45:58Z

Brian: /* Warshall's algorithm */ - note: transitive closure

2011-03-04T20:36:06Z

‎Warshall's algorithm: - note: transitive closure

Brian: renamed section

2011-03-04T20:31:31Z

renamed section

Brian at 20:00, 15 November 2010

2010-11-15T20:00:09Z

Brian at 18:28, 23 December 2009

2009-12-23T18:28:14Z

Jargon: categorize

2009-12-23T17:18:14Z

categorize

Brian at 04:39, 12 December 2009

2009-12-12T04:39:11Z

Brian at 22:06, 6 December 2009

2009-12-06T22:06:18Z

← Older revision		Revision as of 12:16, 25 April 2022
Line 1:		Line 1:
	The '''Floyd–Warshall algorithm''' finds [[Shortest_path#All-pairs_shortest_paths\|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest_path#Single-source_shortest_paths\|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement.		The '''Floyd–Warshall algorithm''' finds [[Shortest_path#All-pairs_shortest_paths\|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest_path#Single-source_shortest_paths\|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement.
		+
		+	==The algorithm==
		+	<pre>
		+	input adj
		+	for each k ∈ V(G)
		+	for each i ∈ V(G)
		+	for each j ∈ V(G)
		+	adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])
		+	for each k ∈ V(G)
		+	if adj[k][k] < 0
		+	error "Graph contains a negative-weight cycle"
		+	</pre>
		+	At the successful conclusion of the algorithm, the adjacency matrix <i>adj</i> will have been transformed into a shortest-paths matrix. If the distance from each vertex to itself is initially set as infinite, this matrix will also tell us the length of the shortest path of nonzero length from each vertex back to itself.

	==Theory of the algorithm==		==Theory of the algorithm==

← Older revision		Revision as of 12:12, 25 April 2022
Line 1:		Line 1:
	The '''Floyd–Warshall algorithm''' finds [[Shortest_path#All-pairs_shortest_paths\|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest_path#Single-source_shortest_paths\|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement.		The '''Floyd–Warshall algorithm''' finds [[Shortest_path#All-pairs_shortest_paths\|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest_path#Single-source_shortest_paths\|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement.
−
−	~~==The algorithm==~~
−	~~<pre>~~
−	~~input adj~~
−	~~for each k ∈ V(G)~~
−	~~for each i ∈ V(G)~~
−	~~for each j ∈ V(G)~~
−	~~adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j])~~
−	~~for each k ∈ V(G)~~
−	~~if adj[k][k] < 0~~
−	~~error "Graph contains a negative-weight cycle"~~
−	~~</pre>~~
−	At the successful conclusion of the algorithm, the adjacency matrix <i>adj</i> will have been transformed into a shortest-paths matrix. If the distance from each vertex to itself is initially set as infinite, this matrix will also tell us the length of the shortest path of nonzero length from each vertex back to itself.

	==Theory of the algorithm==		==Theory of the algorithm==

← Older revision		Revision as of 05:45, 31 May 2011
Line 42:		Line 42:

	[[Category:Algorithms]]		[[Category:Algorithms]]
		+	[[Category:Graph theory]]

@@ Line 28: / Line 28: @@
 ==Warshall's algorithm==
-A special case of the Floyd–Warshall algorithm is ''Warshall's algorithm'', which tests only for reachability. If two vertices are linked by an edge, we assign the edge any finite weight (such as 0 or 1), otherwise we assign it an infinite weight. If, at the end, we find the distance from one vertex to another to be finite, then they are connected, since a path existed using only finite-weight edges (that is, ones that actually exist); otherwise, if no such path exists, the entry in the matrix will be infinity. Notice that we can replace "finite" by 1, "infinite" by 0, addition with logical AND, and <code>min</code> with logical OR, and preserve existing logic. This yields the following implementation of Warshall's algorithm:
+A special case of the Floyd–Warshall algorithm is ''Warshall's algorithm'', which tests only for reachability, hence computing the [[transitive closure]] of a graph. If two vertices are linked by an edge, we assign the edge any finite weight (such as 0 or 1), otherwise we assign it an infinite weight. If, at the end, we find the distance from one vertex to another to be finite, then they are connected, since a path existed using only finite-weight edges (that is, ones that actually exist); otherwise, if no such path exists, the entry in the matrix will be infinity. Notice that we can replace "finite" by 1, "infinite" by 0, addition with logical AND, and <code>min</code> with logical OR, and preserve existing logic. This yields the following implementation of Warshall's algorithm:
 <pre>
 input adj

@@ Line 27: / Line 27: @@
 If no negative-weight edges are present, which is often the case, the final loop may be omitted altogether from the algorithm, since it will never be useful. If negative-weight edges are present, then the final loop will <i>always</i> detect the presence of a negative-weight cycle. Suppose a negative-weight cycle exists. Then, choose any vertex <i>k</i> on this cycle. At the termination of the main loop, <i>dist[k][k]</i> will be negative, since the algorithm will inevitably have found the shortest path from <i>k</i> back to itself using each vertex in the graph at most once (the reason for this is explained in the previous section), which is, of course, of negative weight. (The presence of negative-weight cycles implies the presence of negative-weight simple cycles, as all non-simple cycles can be decomposed into simple cycles.) The algorithm then prints out an appropriate error message.
-==Special case: Warshall's algorithm==
+==Warshall's algorithm==
 A special case of the Floyd–Warshall algorithm is ''Warshall's algorithm'', which tests only for reachability. If two vertices are linked by an edge, we assign the edge any finite weight (such as 0 or 1), otherwise we assign it an infinite weight. If, at the end, we find the distance from one vertex to another to be finite, then they are connected, since a path existed using only finite-weight edges (that is, ones that actually exist); otherwise, if no such path exists, the entry in the matrix will be infinity. Notice that we can replace "finite" by 1, "infinite" by 0, addition with logical AND, and <code>min</code> with logical OR, and preserve existing logic. This yields the following implementation of Warshall's algorithm:
 <pre>

@@ Line 1: / Line 1: @@
-The '''Floyd–Warshall algorithm''' finds [[Shortest path|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest path|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement.
+The '''Floyd–Warshall algorithm''' finds [[Shortest_path#All-pairs_shortest_paths|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest_path#Single-source_shortest_paths|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement.
-=The algorithm=
+==The algorithm==
 <pre>
 input adj
@@ Line 14: / Line 14: @@
 At the successful conclusion of the algorithm, the adjacency matrix <i>adj</i> will have been transformed into a shortest-paths matrix. If the distance from each vertex to itself is initially set as infinite, this matrix will also tell us the length of the shortest path of nonzero length from each vertex back to itself.
-=Theory of the algorithm=
+==Theory of the algorithm==
-==Explanation==
+===Explanation===
 Floyd–Warshall is one of the most well-known examples of a [[dynamic programming]] algorithm. It consists of a single looping structure containing three nested loops and occurs in <math>V</math> passes, where <math>V</math> is the number of vertices in the graph. The graph should be represented as an adjacency matrix <i>adj</i> in order for Floyd–Warshall to be practical, and all missing edges should be assigned infinite weight. After <i>n</i> passes have occurred, the entry <i>adj[u][v]</i> should contain the length of the shortest path from <i>u</i> to <i>v</i> that uses only the first <i>n</i> vertices as possible intermediates along the path. At the termination of the algorithm, after all <math>V</math> passes have occurred, the <i>adj</i> array ought to contain shortest paths that use any vertices whatsoever as intermediates – that which was to be determined.
-==Proof of correctness==
+===Proof of correctness===
 We shall prove the claim above by induction.
 * At the outset, when no passes of the main outer loop have occurred, each entry <i>adj[i][j]</i> contains the shortest distance from <i>i</i> to <i>j</i> using only the first 0 vertices as intermediates: the weight of the edge from <i>i</i> to <i>j</i> itself.
@@ Line 24: / Line 24: @@
 It is also easy to see that the loop at the end will never produce an error, because the shortest path from any vertex back to itself cannot have negative weight unless that vertex is part of a negative-weight cycle.
-==Proof of detection of negative-weight cycles==
+===Proof of detection of negative-weight cycles===
 If no negative-weight edges are present, which is often the case, the final loop may be omitted altogether from the algorithm, since it will never be useful. If negative-weight edges are present, then the final loop will <i>always</i> detect the presence of a negative-weight cycle. Suppose a negative-weight cycle exists. Then, choose any vertex <i>k</i> on this cycle. At the termination of the main loop, <i>dist[k][k]</i> will be negative, since the algorithm will inevitably have found the shortest path from <i>k</i> back to itself using each vertex in the graph at most once (the reason for this is explained in the previous section), which is, of course, of negative weight. (The presence of negative-weight cycles implies the presence of negative-weight simple cycles, as all non-simple cycles can be decomposed into simple cycles.) The algorithm then prints out an appropriate error message.
-=Special case: Warshall's algorithm=
+==Special case: Warshall's algorithm==
 A special case of the Floyd–Warshall algorithm is ''Warshall's algorithm'', which tests only for reachability. If two vertices are linked by an edge, we assign the edge any finite weight (such as 0 or 1), otherwise we assign it an infinite weight. If, at the end, we find the distance from one vertex to another to be finite, then they are connected, since a path existed using only finite-weight edges (that is, ones that actually exist); otherwise, if no such path exists, the entry in the matrix will be infinity. Notice that we can replace "finite" by 1, "infinite" by 0, addition with logical AND, and <code>min</code> with logical OR, and preserve existing logic. This yields the following implementation of Warshall's algorithm:
 <pre>
@@ Line 38: / Line 38: @@
 (<i>Per</i> standard convention, <code>and</code> takes precedence over <code>or</code>.)
-=References=
+==References==
 * Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (1990). ''Introduction to Algorithms'' (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. Section 26.2, "The Floyd–Warshall algorithm", pp. 558–565;
 [[Category:Algorithms]]

← Older revision		Revision as of 17:18, 23 December 2009
Line 37:		Line 37:
	</pre>		</pre>
	(<i>Per</i> standard convention, <code>and</code> takes precedence over <code>or</code>.)		(<i>Per</i> standard convention, <code>and</code> takes precedence over <code>or</code>.)
		+
		+	[[Category:Algorithms]]

← Older revision		Revision as of 04:39, 12 December 2009
Line 1:		Line 1:
−	The '''Floyd–Warshall algorithm''' finds [[Shortest path\|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest path\|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and ~~because it~~ is very easy to implement.	+	The '''Floyd–Warshall algorithm''' finds [[Shortest path\|all-pairs shortest paths]] in a directed, weighted graph which contains no negative-weight cycles. That is, unlike [[Dijkstra's algorithm]], it is guaranteed to correctly compute shortest paths even when some edge weights are negative. (Note however that it is still a requirement that no negative-weight ''cycle'' occurs; finding shortest paths in such a graph becomes either meaningless if non-simple paths are allowed, or computationally difficult when they are not.) With a running time of <math>\mathcal{O}(V^3)</math>, Floyd–Warshall is asymptotically optimal in dense graphs. It is outperformed by [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]] in the [[Shortest path\|single-source shortest paths]] problem (with running times of <math>\mathcal{O}(V^2)</math> and <math>\mathcal{O}(VE)</math>, respectively); in the all-pairs shortest paths problem in a sparse graph, it is outperformed by repeated application of Dijkstra's algorithm and by [[Johnson's algorithm]]. Nevertheless, in small graphs (fewer than about 300 vertices), Floyd–Warshall is often the algorithm of choice, because it computes all-pairs shortest paths, handles negative weights on edges correctly while detecting negative-weight cycles, and is very easy to implement.

	=The algorithm=		=The algorithm=

← Older revision		Revision as of 22:06, 6 December 2009
Line 26:		Line 26:
	==Proof of detection of negative-weight cycles==		==Proof of detection of negative-weight cycles==
	If no negative-weight edges are present, which is often the case, the final loop may be omitted altogether from the algorithm, since it will never be useful. If negative-weight edges are present, then the final loop will <i>always</i> detect the presence of a negative-weight cycle. Suppose a negative-weight cycle exists. Then, choose any vertex <i>k</i> on this cycle. At the termination of the main loop, <i>dist[k][k]</i> will be negative, since the algorithm will inevitably have found the shortest path from <i>k</i> back to itself using each vertex in the graph at most once (the reason for this is explained in the previous section), which is, of course, of negative weight. (The presence of negative-weight cycles implies the presence of negative-weight simple cycles, as all non-simple cycles can be decomposed into simple cycles.) The algorithm then prints out an appropriate error message.		If no negative-weight edges are present, which is often the case, the final loop may be omitted altogether from the algorithm, since it will never be useful. If negative-weight edges are present, then the final loop will <i>always</i> detect the presence of a negative-weight cycle. Suppose a negative-weight cycle exists. Then, choose any vertex <i>k</i> on this cycle. At the termination of the main loop, <i>dist[k][k]</i> will be negative, since the algorithm will inevitably have found the shortest path from <i>k</i> back to itself using each vertex in the graph at most once (the reason for this is explained in the previous section), which is, of course, of negative weight. (The presence of negative-weight cycles implies the presence of negative-weight simple cycles, as all non-simple cycles can be decomposed into simple cycles.) The algorithm then prints out an appropriate error message.
		+
		+	=Special case: Warshall's algorithm=
		+	A special case of the Floyd–Warshall algorithm is ''Warshall's algorithm'', which tests only for reachability. If two vertices are linked by an edge, we assign the edge any finite weight (such as 0 or 1), otherwise we assign it an infinite weight. If, at the end, we find the distance from one vertex to another to be finite, then they are connected, since a path existed using only finite-weight edges (that is, ones that actually exist); otherwise, if no such path exists, the entry in the matrix will be infinity. Notice that we can replace "finite" by 1, "infinite" by 0, addition with logical AND, and <code>min</code> with logical OR, and preserve existing logic. This yields the following implementation of Warshall's algorithm:
		+	<pre>
		+	input adj
		+	for each k ∈ V(G)
		+	for each i ∈ V(G)
		+	for each j ∈ V(G)
		+	adj[i][j] = adj[i][j] or adj[i][k] and adj[k][j]
		+	</pre>
		+	(<i>Per</i> standard convention, <code>and</code> takes precedence over <code>or</code>.)