Floyd - Warshall - Shortest Path Graphs description of Floyd - Warshall and its uses in graghs

[andresmtz 0]

Floyd - Warshall

 

The Floyd - Warshall algorithm is used to find the shortest path between all nodes in a directed graph with weights in its connections.

 

A single run of the algorithm will find the shortest path between any pair of nodes in the graph with a complexity time of O(V^3), where V is the number of nodes of the graph. This complexity time is due to the 3 cycles it uses in its implementation.

 

The algorithm works by estimating the cost of the shortest path between nodes and it corrects its answer in each iteration.

 

Let's suppose that we have a graph with V nodes, all numbered from 1 to N.

The shortest path between node 'i' and node 'j' could be one of the followings:

- The path between "i" and "j" or

- The path between "i" and "k" plus the shortest path between "k" and "j", where "k: is the intermediate node smaller than N

 

In other words these two statements could be written as pseudo code:

shortestPath_i_to_j = min(shortestPath(i, j), shortestPath(j, k) + shortestPath(k, i));

 

And the complete pseudo code is:

 

procedure FloydWarshall ()

for k = 1 to n

for each (i,j) in (1..n)

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

end

end

end procedure

 

Assume that N is the number of nodes in the graph and that each element of the path[j] has been initialize with the cost of traveling from i to j, normally using an adjacency matrix.

 

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). Nevertheless, if there are negative cycles, Floyd–Warshall can be used to detect them: either run one more iteration and see if there are any changes, or look for negative values in the diagonal.

 

Some of its applications and problems were it could be applied are

- Shortest paths in directed graphs.

- Transitive closure of directed graphs. 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) (sound complex? yes!)

- Inversion of real matrices (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.

 

 

Hope this was useful to understand the algorithm and that you will be able to apply this algorithm in solving problems.