Explanation of algorithm - Reach-ability matrix

Question

I found the following:

Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph.

Here reachable means that there is a path from vertex i to j.

The reach-ability matrix is called transitive closure of a graph.

The graph is given in the form of adjacency matrix say ‘graph[V][V]’ where graph[i][j] is 1 if there is an edge from vertex i to vertex j or i is equal to j, otherwise graph[i][j] is 0.

We can calculate the distance matrix dist[V][V] using Floyd Warshall, if dist[i][j] is infinite, then j is not reachable from i, otherwise j is reachable and value of dist[i][j] will be less than V.

// Prints transitive closure of graph[][] using Floyd Warshall algorithm
void transitiveClosure(int graph[][V])
{
    /* reach[][] will be the output matrix that will finally have the shortest
      distances between every pair of vertices */
    int reach[V][V], i, j, k;
 
    /* Initialize the solution matrix same as input graph matrix. Or
       we can say the initial values of shortest distances are based
       on shortest paths considering no intermediate vertex. */
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            reach[i][j] = graph[i][j];
 
    /* Add all vertices one by one to the set of intermediate vertices.
      ---> Before start of a iteration, we have reachability values for all
      pairs of vertices such that the reachability values consider only the
      vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
      ----> After the end of a iteration, vertex no. k is added to the set of
      intermediate vertices and the set becomes {0, 1, 2, .. k} */
    for (k = 0; k < V; k++)
    {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++)
        {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++)
            {
                // If vertex k is on a path from i to j,
                // then make sure that the value of reach[i][j] is 1
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }
 
    // Print the shortest distance matrix
    printSolution(reach);
}

First of all, could you explain me why the argument of the function is graph[][V] and not for example graph[V][V] ?

Then why do we initialize the matrix, that will finally have the shortest distances between every pair of vertices, with graph[V][V]?

And could you explain me what is done after the initialization, in the for-loops?

How could we write this command: reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]); elsewhise?

EDIT: graph is a boolean matrix, or not?

If so, then isn't reach also a boolean matrix?

So if we have this command: ( reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]); ) and if reach[i][j]=1 then do we execute this: reach[i][j]=reach[i][j], elsewhise we check if (reach[i][k] + reach[k][j]) is non-zero?

Or have I understood it wrong?

Answer 1

First of all, could you explain me why the argument of the function is graph[][V] and not for example graph[V][V] ?

It could be graph[V][V] aswell. I would prefer graph[V][V] as this is the expected input anyways.

Then why do we initialize the matrix, that will finally have the shortest distances between every pair of vertices, with graph[V][V]?

That is because distance between the nodes a and b will definitely be at most the value of the edge between a and b (assuming it is infinite if there is no edge). E. g.: if we have graph where there is edge between A and B with length 5, we know for sure that there exists path between A and B of length 5 for sure, however there might exist shorter path.

There is something important to note here. If you are only interested in reachability, than you don't care about the actual distances. In that case you can just set a value to 0 if there doesn't exist any path and to 1 if there exists a path.

And could you explain me what is done after the initialization, in the for-loops?

You are basically using dynamic programming approach. Explanation is pretty long, read about it here: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

How could we write this command: reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]); elsewhise?

We could write it as: reach[i][j] |= (reach[i][k] && reach[k][j])

Answer 2

First of all, could you explain me why the argument of the function is graph[][V] and not for example graph[V][V] ?

The function is declared that way so it can accept a two-dimensional array of which one axis is of an unknown size. Since an adjacency matrix is square by definition and reach[V][V] is defined later, I have no idea why they would define the function this way. See this SO question for more details.

Then why do we initialize the matrix, that will finally have the shortest distances between every pair of vertices, with graph[V][V]?

graph defines every vertex which can reach every other vertex by traversing a single edge with no intermediate nod. When we begin the algorithm, these are the shortest paths and only paths we know to get from one vertex to another. Usually if vertexes are unreachable from each other via a direct path, graph will define that edge to be zero (no connectivity) or infinite (the distance between them is so huge as to be impassable).

And could you explain me what is done after the initialization, in the for-loops?

First, understand this line:

reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

It asks: "Is vertex i reachable from vertex j? OR Can vertex i be reached from vertex j by passing through an intermediate vertex k?"

That explains why you need three for loops. Why are they ordered like they are?

Imagine you had the same line as above with the for loops ordered like so:

for i
  for j
    for k

If this were the case, for each pair of vertices (i,j) you would check to see if the two could be connected by some intermediate vertex k. And then you'd quit.

But what if you have to pass through two intermediate vertices to get from (i,j). The above ordering of the for loops may not discover this possibility.

Instead, we order the for loops with k on the outside and, therefore, find all the pairs of points for which k is an intermediate point. We then do this for each possible intermediate point k. There are rigorous ways to prove that doing this will allow you to consider all paths between two points, but, if you think about it for a bit, I think you'll find it to be intuitively true.

How could we write this command: reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]); elsewise?

As another commentator has said, you could write:

reach[i][j] |= (reach[i][k] && reach[k][j])

You could also write:

reach[i][j] = min(reach[i][j], reach[i][k]+reach[k][j])

which would find the length of the shortest path between two vertices, provided your input graph uses infinity to represent non-connected vertices.

Note that this:

reach[i][j] = max(reach[i][j], reach[i][k]+reach[k][j])

would be a very bad idea. Finding the longest path in a general graph is NP-hard: we know of no good way of doing it and there probably isn't one. But, if you find one, you will not only be rich: the entire world will change overnight and you will be remembered forever.