Floyd Warshall Algorithm

From "A B C"
Revision as of 19:44, 7 April 2012 by Boris (talk | contribs) (Created page with "<div id="APB"> <div class="b1"> Floyd-Warshall Algorithm </div> The Floyd-Warshall algorithm is a graph-analysis algorithm that calculates '''shortest paths between all pair...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Floyd-Warshall Algorithm


The Floyd-Warshall algorithm is a graph-analysis algorithm that calculates shortest paths between all pairs of nodes in a graph. It is a dynamic programming algorithm with O(|V|3) time complexity and O(|V|2) space complexity. For path reconstruction, see here; for a more efficient algorithm for sparse graphs, see Johnson's algorithm.



 

Contents

Original source taken from Floyd-Warshall algorithm.


 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathit{k} := 1}
 to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathit{n}}

14       for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathit{(i,j)}}
 in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lbrace 1,..,n \rbrace^2}

15          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );


   

Further reading and resources