In this section, we look at two well-known algorithms: Warshall’s algorithm for computing the transitive closure of a directed graph and Floyd’s algorithm for the all-pairs shortest-paths problem.

**Warshall’s and Floyd’s Algorithms**

In this section, we look at two well-known algorithms: Warshall’s algorithm for computing the transitive closure of a directed graph and Floyd’s algorithm for the all-pairs shortest-paths problem. These algorithms are based on essentially the same idea: exploit a relationship between a problem and its simpler rather than smaller version. Warshall and Floyd published their algorithms without mention-ing dynamic programming. Nevertheless, the algorithms certainly have a dynamic programming flavor and have come to be considered applications of this tech-nique.

**Warshall’s Algorithm**

Recall that the adjacency matrix ** A** = {

Here are a few application examples. When a value in a spreadsheet cell is changed, the spreadsheet software must know all the other cells affected by the change. If the spreadsheet is modeled by a digraph whose vertices represent the spreadsheet cells and edges indicate cell dependencies, the transitive closure will provide such information. In software engineering, transitive closure can be used for investigating data flow and control flow dependencies as well as for inheritance testing of object-oriented software. In electronic engineering, it is used for redundancy identification and test generation for digital circuits.

**DEFINITION **The** ***transitive closure*** **of a directed graph with** n **vertices can be

An example of a digraph, its adjacency matrix, and its transitive closure is given in Figure 8.11.

We can generate the transitive closure of a digraph with the help of depth-first search or breadth-first search. Performing either traversal starting at the ** i**th

vertex gives the information about the vertices reachable from it and hence the columns that contain 1’s in the ** i**th row of the transitive closure. Thus, doing such a traversal for every vertex as a starting point yields the transitive closure in its entirety.

Since this method traverses the same digraph several times, we should hope that a better algorithm can be found. Indeed, such an algorithm exists. It is called ** Warshall’s algorithm **after Stephen Warshall, who discovered it [War62]. It is

Each of these matrices provides certain information about directed paths in the digraph. Specifically, the element *r**ij*** (k)** in the

The central point of the algorithm is that we can compute all the elements of each matrix *R*** (k)** from its immediate predecessor

*v**i*** , **a list of intermediate vertices each numbered not higher than

Two situations regarding this path are possible. In the first, the list of its inter-mediate vertices does not contain the ** k**th vertex. Then this path from

intermediate vertices numbered not higher than ** k** − 1

*v**i*** , **vertices numbered

The first part of this representation means that there exists a path from *v*** i** to

What we have just proved is that if *r**ij*** (k)** = 1

true. Thus, we have the following formula for generating the elements of matrix *R**(k)*** **from the elements of matrix

Formula (8.11) is at the heart of Warshall’s algorithm. This formula implies the following rule for generating elements of matrix *R*** (k)** from elements of matrix

If an element *r*** ij** is 1 in

If an element *r*** ij** is 0 in

** k **are both 1’s in

As an example, the application of Warshall’s algorithm to the digraph in Figure 8.11 is shown in Figure 8.13.

Here is pseudocode of Warshall’s algorithm.

**ALGORITHM** *Warshall*** (A**[1

//Implements Warshall’s algorithm for computing the transitive closure //Input: The adjacency matrix ** A** of a digraph with

//Output: The transitive closure of the digraph

*R*** (**0

**for ***k*** **←** **1** to ***n*** do for ***i*** **←** **1** to ***n*** do**

**for ***j*** **←** **1** to ***n*** do**

*R*** (k)**[

**return ***R**(n)*

Several observations need to be made about Warshall’s algorithm. First, it is remarkably succinct, is it not? Still, its time efficiency is only ** $(n**3

mentioned at the beginning of this section has a better asymptotic efficiency than Warshall’s algorithm (why?). We can speed up the above implementation of Warshall’s algorithm for some inputs by restructuring its innermost loop (see Problem 4 in this section’s exercises). Another way to make the algorithm run faster is to treat matrix rows as bit strings and employ the bitwise *or* operation available in most modern computer languages.

As to the space efficiency of Warshall’s algorithm, the situation is similar to that of computing a Fibonacci number and some other dynamic programming algorithms. Although we used separate matrices for recording intermediate results of the algorithm, this is, in fact, unnecessary. Problem 3 in this section’s exercises asks you to find a way of avoiding this wasteful use of the computer memory. Finally, we shall see below how the underlying idea of Warshall’s algorithm can be applied to the more general problem of finding lengths of shortest paths in weighted graphs.

**Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem**

Given a weighted connected graph (undirected or directed), the ** all-pairs shortest-paths problem **asks to find the distances—i.e., the lengths of the shortest paths—

It is convenient to record the lengths of shortest paths in an ** n** ×

We can generate the distance matrix with an algorithm that is very similar to Warshall’s algorithm. It is called ** Floyd’s algorithm** after its co-inventor Robert W. Floyd.1 It is applicable to both undirected and directed weighted graphs provided that they do not contain a cycle of a negative length. (The distance between any two vertices in such a cycle can be made arbitrarily small by repeating the cycle enough times.) The algorithm can be enhanced to find not only the lengths of the shortest paths for all vertex pairs but also the shortest paths themselves (Problem 10 in this section’s exercises).

Floyd’s algorithm computes the distance matrix of a weighted graph with ** n** vertices through a series of

Each of these matrices contains the lengths of shortest paths with certain con-straints on the paths considered for the matrix in question. Specifically, the el-ement *d**ij*** (k)** in the

As in Warshall’s algorithm, we can compute all the elements of each matrix *D**(k)*** **from its immediate predecessor

*v**i*** , **a list of intermediate vertices each numbered not higher than

We can partition all such paths into two disjoint subsets: those that do not use the ** k**th vertex

What is the length of the shortest path in the second subset? If the graph does not contain a cycle of a negative length, we can limit our attention only to the paths in the second subset that use vertex *v*** k** as their intermediate vertex exactly once (because visiting

*v**i*** , **vertices numbered

In other words, each of the paths is made up of a path from *v*** i** to

Since the length of the shortest path from *v*** i** to

vertices numbered not higher than ** k** − 1 is equal to

path among the paths that use the ** k**th vertex is equal to

To put it another way, the element in row ** i** and column

The application of Floyd’s algorithm to the graph in Figure 8.14 is illustrated in Figure 8.16.

Here is pseudocode of Floyd’s algorithm. It takes advantage of the fact that the next matrix in sequence (8.12) can be written over its predecessor.

**ALGORITHM** *Floyd**(W** *[1*..n,** *1** ..n**]

//Implements Floyd’s algorithm for the all-pairs shortest-paths problem //Input: The weight matrix ** W** of a graph with no negative-length cycle //Output: The distance matrix of the shortest paths’ lengths

** D **←

**for ***i*** **←** **1** to ***n*** do**

**for ***j*** **←** **1** to ***n*** do**

** D**[

**return ***D*

Obviously, the time efficiency of Floyd’s algorithm is cubic—as is the time efficiency of Warshall’s algorithm. In the next chapter, we examine Dijkstra’s algorithm—another method for finding shortest paths.

**Exercises 8.4**

Apply Warshall’s algorithm to find the transitive closure of the digraph de-fined by the following adjacency matrix:

** ****a. **Prove that the time efficiency of Warshall’s algorithm is cubic.

Explain why the time efficiency class of Warshall’s algorithm is inferior to that of the traversal-based algorithm for sparse graphs represented by their adjacency lists.

** **Explain how to implement Warshall’s algorithm without using extra memory for storing elements of the algorithm’s intermediate matrices.

** **Explain how to restructure the innermost loop of the algorithm *Warshall* to make it run faster at least on some inputs.

** **Rewrite pseudocode of Warshall’s algorithm assuming that the matrix rows are represented by bit strings on which the bitwise *or* operation can be per-formed.

** ****a. **Explain how Warshall’s algorithm can be used to determine whether a** **given digraph is a dag (directed acyclic graph). Is it a good algorithm for this problem?

** **Is it a good idea to apply Warshall’s algorithm to find the transitive closure of an undirected graph?

** **Solve the all-pairs shortest-path problem for the digraph with the following

weight matrix:

** **Prove that the next matrix in sequence (8.12) of Floyd’s algorithm can be written over its predecessor.

** **Give an example of a graph or a digraph with negative weights for which Floyd’s algorithm does not yield the correct result.

** **Enhance Floyd’s algorithm so that shortest paths themselves, not just their lengths, can be found.

*Jack Straws *In the game of Jack Straws, a number of plastic or wooden* *“straws” are dumped on the table and players try to remove them one by one without disturbing the other straws. Here, we are only concerned with whether various pairs of straws are connected by a path of touching straws. Given a list of the endpoints for ** n >** 1 straws (as if they were dumped on a large piece of graph paper), determine all the pairs of straws that are connected. Note that touching is connecting, but also that two straws can be connected indirectly via other connected straws. [1994 East-Central Regionals of the ACM International Collegiate Programming Contest]

**SUMMARY**

*Dynamic programming *is a technique for solving problems with overlapping* *subproblems. Typically, these subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems of the same type. Dynamic programming suggests solving each smaller subproblem once and recording the results in a table from which a solution to the original problem can be then obtained.

Applicability of dynamic programming to an optimization problem requires the problem to satisfy the *principle of optimality*: an optimal solution to any of its instances must be made up of optimal solutions to its subinstances.

Among many other problems, the *change-making problem* with arbitrary coin denominations can be solved by dynamic programming.

Solving a knapsack problem by a dynamic programming algorithm exempli-fies an application of this technique to difficult problems of combinatorial optimization.

The *memory function* technique seeks to combine the strengths of the top-down and bottom-up approaches to solving problems with overlapping subproblems. It does this by solving, in the top-down fashion but only once, just the necessary subproblems of a given problem and recording their solutions in a table.

Dynamic programming can be used for constructing an *optimal binary search* *tree *for a given set of keys and known probabilities of searching for them.

*Warshall’s algorithm *for finding the* transitive closure *and* Floyd’s algorithm *for the *all-pairs shortest-paths problem* are based on the idea that can be interpreted as an application of the dynamic programming technique.

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

Introduction to the Design and Analysis of Algorithms : Dynamic Programming : Warshall’s and Floyd’s Algorithms |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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