Dynamic Programming

Warshall’s Algorithm

Page 330

Warshall’s Algorithm is a well-known algorithm used to compute the transitive closure of a directed graph. This algorithm is categorized under dynamic programming because it exploits a relationship between a problem and its simpler, rather than smaller, version.

The transitive closure of a directed graph with 'n' vertices is an 'n × n' boolean matrix, denoted as T = {tij}.

In this matrix:

• An element tij is 1 if there exists a nontrivial path (a directed path of positive length) from the 'ith' vertex to the 'jth' vertex.
• Otherwise, tij is 0.

The transitive closure provides valuable information, such as determining in constant time whether the 'jth' vertex is reachable from the 'ith' vertex.

ALGORITHM Warshall(A[1..n, 1..n])
// Implements Warshall’s algorithm for computing the transitive closure
// Input: The adjacency matrix A of a digraph with n vertices
// Output: The transitive closure of the digraph

R(0) ← A
for k ← 1 to n do
    for i ← 1 to n do
        for j ← 1 to n do
            R(k)[i, j] <- R(k-1)[i, j] OR (R(k-1)[i, k] AND R(k-1)[k, j])
return R(n)

Algorithm Warshall(R, n):
// R: adjacency matrix of the graph (n × n)
// n: number of vertices
// Output: transitive closure matrix T

// Initialize transitive closure as R
Let T[0..n-1, 0..n-1] <- R

// Iteratively update transitive closure
for k <- 0 to n-1 do
	for i <- 0 to n-1 do
		for j <- 0 to n-1 do
			T[i][j] <- T[i][j] OR (T[i][k] AND T[k][j])

return T

The core of the algorithm lies in computing each matrix R(k) from its immediate predecessor matrix R(k-1) using the following rule:

Let r(k)ij be the element in the 'ith' row and 'jth' column of matrix R(k).

• If r(k-1)ij is 1, it remains 1 in R(k). This signifies a path already exists without using vertex 'k' as an intermediate.

• If r(k-1)ij is 0, it changes to 1 in R(k) if and only if there is a path from vertex 'vi' to vertex 'vk' (represented by r(k-1)ik = 1) AND there is a path from vertex 'vk' to vertex 'vj' (represented by r(k-1)kj = 1). This essentially means that a path from 'vi' to 'vj' now exists through 'vk'.

• If there is a path from i to k and from k to j, then there is a path from i to j.

This rule is expressed by the formula: R(k)[i, j] ← R(k-1)[i, j] OR (R(k-1)[i, k] AND R(k-1)[k, j]).

Efficiency and Observations

• Time Efficiency: Warshall's algorithm has a time efficiency of Θ(n³). This is derived from the three nested loops, each running 'n' times, and the constant-time boolean operations inside.

• Space Efficiency: Although the pseudocode suggests using separate matrices for intermediate results, this is not strictly necessary. The algorithm can be implemented by overwriting the matrix in place.

• Comparisons with Traversal-based Algorithms: For sparse graphs (where the number of edges |E| is proportional to the number of vertices |V|), traversal-based algorithms (DFS or BFS, run |V| times) can have a better asymptotic efficiency, specifically Θ(|V|²) or Θ(|V|² + |V||E|) with adjacency lists, compared to Warshall's Θ(|V|³) **.

Floyd’s Algorithm

Floyd’s Algorithm is a renowned dynamic programming algorithm designed to solve the all-pairs shortest-paths problem in a weighted connected graph.

The All-Pairs Shortest Paths Problem

The all-pairs shortest-paths problem aims to find the lengths of the shortest paths from every vertex to all other vertices within a given weighted connected graph.

This problem is applicable to both undirected and directed graphs, provided they do not contain a cycle of negative length.

The results are typically stored in an n × n distance matrix (D), where the element dij represents the length of the shortest path from the ith vertex to the jth vertex.

Floyd's algorithm constructs the final distance matrix through a series of n × n matrices, denoted as D(0), D(1), ..., D(k), ..., D(n).

• D(0): This is the initial matrix, which is simply the weight matrix (W) of the graph. It represents paths that use no intermediate vertices.

• D(k): Each subsequent matrix D(k) contains the lengths of shortest paths where all intermediate vertices on the path. The intermediate vertices are numbered no higher than k.

• D(n): The final matrix, D(n), is the algorithm's output. It contains the lengths of shortest paths using all n vertices as potential intermediate points, effectively representing the complete distance matrix of the graph.

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 n vertices and no negative-length cycle
// Output: The distance matrix of the shortest paths’ lengths

D ← W               // Initialize D with the weight matrix.

for k ← 1 to n do       // k represents the intermediate vertex
    for i ← 1 to n do     // i represents the starting vertex
        for j ← 1 to n do     // j represents the ending vertex
            D[i, j] ← min( D[i, j], D[i, k] + D[k, j] )

return D

Algorithm Floyd(W, n):
// W: weight matrix of the graph (n × n)
// W[i][j] is the weight of edge (i, j), or ∞ if no edge exists
// n: number of vertices
// Output: distance matrix D containing shortest path lengths

Let D[0..n-1, 0..n-1] <- W

for k <- 0 to n-1 do
	for i <- 0 to n-1 do
		for j <- 0 to n-1 do
			if D[i][k] + D[k][j] < D[i][j] then
				D[i][j] <- D[i][k] + D[k][j]

return D

Efficiency

• Time Efficiency: Floyd's algorithm has a time efficiency of Θ(n³). This is due to the three nested loops, each iterating n times, with constant-time operations inside.

• Space Efficiency: The algorithm can be implemented with Θ(n²) space by overwriting the matrix in place, meaning it only requires space for the distance matrix itself.

---

This problem has significant applications in various fields, including:

• Transportation planning.
• Packet routing in communication networks like the Internet.
• Precomputing distances for motion planning in computer games.
• Finding shortest paths in social networks, speech recognition, document formatting, robotics, and compilers.