Editing Floyd–Warshall algorithm (section)

==Behavior with negative cycles==

A negative cycle is a cycle whose edges sum to a negative value.  There is no shortest path between any pair of vertices <math>i</math>, <math>j</math> which form part of a negative cycle,  because path-lengths from <math>i</math> to <math>j</math> can be arbitrarily small (negative).  For numerically meaningful output, the Floyd–Warshall algorithm assumes that there are no negative cycles.  Nevertheless, if there are negative cycles, the Floyd–Warshall algorithm can be used to detect them.  The intuition is as follows:

* The Floyd–Warshall algorithm iteratively revises path lengths between all pairs of vertices <math>(i,j)</math>, including where <math>i=j</math>;
* Initially, the length of the path <math>(i,i)</math> is zero;
* A path <math>[i,k,\ldots,i]</math> can only improve upon this if it has length less than zero, i.e. denotes a negative cycle;
* Thus, after the algorithm, <math>(i,i)</math> will be negative if there exists a negative-length path from <math>i</math> back to <math>i</math>.

Hence, to detect negative [[Cycle (graph theory)|cycles]] using the Floyd–Warshall algorithm, 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.<ref name=":1">{{cite web |last=Hochbaum |first=Dorit |author-link=Dorit S. Hochbaum |date=2014 |title=Section 8.9: Floyd-Warshall algorithm for all pairs shortest paths |url=http://www.ieor.berkeley.edu/~hochbaum/files/ieor266-2014.pdf |work=Lecture Notes for IEOR 266: Graph Algorithms and Network Flows |publisher=Department of Industrial Engineering and Operations Research, [[University of California, Berkeley]] |pages=41–42}}</ref> However, when a negative cycle is present, during the execution of the algorithm exponentially large numbers on the order of <math>\Omega(6^n \cdot w_{max})</math> can appear, where <math>w_{max}</math> is the largest absolute value edge weight in the graph. To avoid integer underflow problems, one should check for a negative cycle within the innermost for loop of the algorithm.<ref>
{{cite journal
 | title =   The Floyd–Warshall algorithm on graphs with negative cycles
 | author =  Stefan Hougardy
 | journal = Information Processing Letters
 | volume = 110 
 | number = 8–9
 | date = April 2010
 | pages = 279–281
 | doi=10.1016/j.ipl.2010.02.001
}}</ref>