Warshall's algorithm uses the adjacency matrix to find the transitive closure of a directed graph.
The transitive closure of a directed graph with n vertices can be defined as the n-by-n boolean matrix T, in which the element in the ith row and jth column is 1 if there exist a directed path from the ith vertex to the jth vertex, otherwise it is zero.
Graphical Examples
Transitive Closure can be solved by graph transversal for each vertex in the graph. If a vertex is reached then the corresponding matrix element is filled with 1. Assuming that the graph was represented by an adjacency matrix then the cost is Θ(n3) where n is the number of vertices in the graph. For a sparse graph, adjacency list is more appropriate, then the cost is Θ((n+m)n).
Warshall's algorithm calculates the transitive closure by generating a sequence of n matrices, where n is the number of vertices.
R(0), ..., R(k-1), R(k), ... , R(n)
Recall that a path in a simple graph can be defined by a sequence of vertices.
The definition of the element at the ith row and jth column in the kth matrix (R(k)), rij(k) is one if and only if there exist a path from vi to vj such that all the intermediate vertex, wq is among the first k vertices, ie. 1 ≤ q ≤ k.
The R(0) matrix represent paths without any intermediate vertices, so it is the adjacency matrix. The R(n) matrix has ones if there is a path between the vertices with intermediate vertices from any of the n vertices of the graph, so it is the transitive closure.
Consider the case rij(k) is one and rij(k-1) = 0. This can occur only if that there is an intermediate path through vk from from vi to vj. More specifically the list of vertices has the form
vi, wq (where 1 ≤ q < k), vk. wq (where 1 ≤ q < k), vj
This can happen only if rik(k-1) = rkj(k-1) = 1. Note the k subscript
If rij(k-1) = 1 then rij(k) should be one.
In sumarry
rij(k) = rij(k-1) or (rik(k-1) and rkj(k-1))
Illustrate the algorithm, point out the rows and columns being referenced in each matrix
Algorithm Warshall(A[1...n, 1...n]) // A is the adjacency matrix
R(0) ←
A
for k ← 1 to n do
for i ← 1 to n do
for j ← 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)
The worst case cost is Θ(n3), so it is not better than the brute force algorithm. In fact, for a sparse graph the brute force algorithm is faster.
Note that separate R matrix need not be stored.
The shortest path in a weighted graph is the minimum sum of weighted edges for all paths between the pair. All pairs shortest path problem is to finding the minimum weight path between any two vertices in the graph.
The distant matrix gives the weight of edges for adjacent vertices. Note that if the two vertices are not adjacent then the corresponding distant matrix entry is ∞.
Brute Force Algorithm is to use a graph transversal for each vertex. Assuming that the graph is represented by an adjacency matrix then the cost is Θ(n3) where n is the number of vertices in the graph. For a spare graph and adjacency list then the cost is Θ((n+m)n).
Floyd's Algorithm is very similar to Warshall's algorithm calculates the minimal distance using a sequence of n matrices, where n is the number of vertices
D(0), ..., D(k-1), D(k), ... , D(n)
The i, j entry in D(k), dij(k), is the minimal distance of path between vertices, vi to vj such that all the intermediate vertex, wq is among the first k vertices, ie. 1 ≤ q ≤ k.
Note that D(0) is the distance matrix and D(n) is the solution that we are seeking.
Consider the all the paths from vi to vj with intermediate vertices less than k, they can be divided into sets:
1. Paths with no vertex numbered k
2. Paths with a vertex numbered k
In set 1, all paths with no vertex numbered k, the minimal distance is dij(k-1)
In set 2, all paths with a vertex numbered k, the minimal path will visit the vk only once. Why? Then the paths be split into parts at vk:
vi, wq (where 1 ≤ q < k), vk. wq (where 1 ≤ q < k), vj
Note: vi, wq (where 1 ≤ q < k), vk are the paths from vi to vk with no intermediate vk. The minimal is dik(k-1).
Also: vk.
wq
(where 1 ≤ q < k), vj
are the paths from vk
to vj
with no intermediate vk.
The minimal is dkj(k-1).
The shortest path for set 2 is min(dik(k-1) + dkj(k-1)).
Let W represent the weight of the path. Then
WP({vi,...,vj}) = ∑i<q≤jD[q-1, q]
The minimal path from vi to vj is then the minimal of the two sets:
or dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1))
Algorithm Floyd(W[1...n, 1...n]) // W is the weight distances
D(0) ← W
for k ← 1 to n do // iteration through distance matrices
for i ← 1 to n do
for j ← to n do
D(k)[i, j] ← min(D(k-1)[i, j], (D(k-1)[i, k] + D(k-1)[k, j]))
return D(n)
Cost is Θ(n3)
Illustrate
Note that only the prior distance matrix need only be stored.