Question

Problem 2: As we discussed in class, one can use an algorithm for computing all-pairs shortest paths to also compute the transitive closure of a graph. If using Floyd-Warshall for example, it is possible to do this in On") time (where as usual n is the number of nodes and m is the number of edges). Show how to compute the transitive closure of a directed graph in O(nm) time. For which type of graphs is this better than using Floyd-Warshall?

Answer 1

All-Pairs Shortest Paths: Suppose that we want instead to compute shortest paths between all pairs of vertices.
We could do this applying either Dijkstra or Bellman-Ford using every vertex as a source, but
today we will consider an alternative approach, which is based on dynamic programming.
Let G = (V, E) be a directed graph with edge weights. For each edge (u, v) E, let w(u, v)
denote its weight. The cost of a path is the sum of its edge weights, and the distance between
two vertices, denoted δ(u, v), minimum cost of any path between u and v. As in Bellman-
Ford, we allow negative cost edges, but no negative-cost cycles. (Recall that negative-cost
cycles imply that shortest paths are not defined.)
The algorithm that we will present is called the Floyd-Warshall algorithm. It runs in O(n
3
)
time, where n = |V |. It dates back to the early 1960’s. The algorithm can be adapted for use
in a number of related applications as well.
Transitive Closure: You are given a binary relation R on a set X, by which we mean that
R is a subset of ordered pairs (x, y) ⊆ X × X. A relation is said to be transitive if for
any x, y, z ∈ X, if (x, y) ∈ R and (y, z) ∈ R then (x, z) ∈ R. The transitive closure of
R, denoted R∗
is the smallest extension of R that is transitive.
We can think of (X, R) as a directed graph, where X are the vertices and the pairs of R
are edges. The transitive closure of R is effectively the same as the reachability relation
in this graph, that is, (x, y) ∈ R∗
if and only if there exists a path from x to y in R.
The Floyd-Warshall algorithm can be modified to compute the transitive closure in time
O(n
3
), where n = |X|.

It seems that for sparse graphs with weighted edges Dijkstra’s algorithm it more useful, because it runs faster than Floyd-Warshall one. For other graphs it is better to use Floyd-Warshall to compute the shortest path., because Dijkstra’s one would fail here.