Home | | Programming and Data Structure II | Floyd - Warshall Algorithm

# Floyd - Warshall Algorithm

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 = <v1, v2, ..., vj> is any vertex other than v1 or vj.

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 p1 and p2 giving vi ÔćŁ k ÔćŁ vj

Ôçĺ Subpaths p1 and p2 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(V3).

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 dij < n

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Graphs : Floyd - Warshall Algorithm |