The Floyd-Warshall algorithm works based on a property of intermediate vertices of a shortest path.

__FLOYD -
WARSHALL ALGORITHM____:__

The
Floyd-Warshall algorithm works based on a property of *intermediate* vertices of a shortest path. An *intermediate* vertex for a path *p*
= <*v*_{1}, *v*_{2}, ..., *v*_{j}> is any vertex other than *v*_{1} or *v*_{j}.

If the
vertices of a graph *G* are indexed by
{1, 2, ..., *n*}, then consider a
subset of vertices {1, 2, ..., *k*}.
Assume *p* is a minimum weight path
from vertex *i* to vertex *j* whose intermediate vertices are drawn
from the subset {1, 2, ..., *k*}. If we
consider vertex *k* on the path then
either:

·
*k *is* ***not*** *an intermediate vertex of* p *(i.e. is not used in the minimum
weight path)

⇒ All
intermediate vertices are in {1, 2, ..., *k*-1}

·
*k *is an
intermediate vertex of* p *(i.e. is
used in the minimum weight path)

⇒ We can
divide *p* at *k* giving two subpaths *p*_{1}
and *p*_{2} giving *v*_{i} ↝ *k* ↝ *v*_{j}

⇒ Subpaths *p*_{1} and *p*_{2} are shortest paths with intermediate vertices in {1,
2, ..., *k*-1}

Thus if
we define a quantity *d*^{(k)}_{ij}
as the minimum weight of the path from vertex *i* to vertex *j* with
intermediate vertices drawn from the set {1, 2, ..., *k*} the above properties give the following recursive solution

Thus we
can represent the optimal values (when *k*
= *n*) in a matrix as

Basically
the algorithm works by repeatedly exploring paths between every pair using each
vertex as an intermediate vertex. Since Floyd-Warshall is simply three (tight)
nested loops, the run time is clearly O(*V*^{3}).

__Example:__

*Initialization*: (*k *= 0)

*Iteration 1*: (*k *= 1) Shorter paths from 2* *↝* *3 and 2* *↝* *4 are
found through vertex 1

*Iteration 2*: (*k *= 2) Shorter paths from 4* *↝* *1, 5* *↝* *1, and 5* *↝* *3 are
found through vertex 2

*Iteration 3*: (*k *= 3) No shorter paths are found through vertex 3

*Iteration 4*: (*k *= 4) Shorter paths from 1* *↝* *2, 1* *↝* *3, 2* *↝* *3, 3* *↝* *1, 3* *↝* *2, 5* *↝* *1, 5* *↝* *2, 5* *↝* *3, and 5 ↝ 4 are found through vertex 4

*Iteration 5*: (*k *= 5) No shorter paths are found through vertex 5

The final
shortest paths for all pairs is given by

**Transitive Closure**

Floyd-Warshall
can be used to determine whether or not a graph has *transitive closure*, i.e. whether or not there are paths between all
vertices.

·
Assign all edges in the graph to have weight = 1

·
Run Floyd-Warshall

· Check if *all d*_{ij} < *n*

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Graphs : Floyd - Warshall Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.