algorithm - 算法说明 - 可达性矩阵

Question

我发现了以下内容:

给定一个有向图，对于给定图中的所有顶点对 (i, j)，找出顶点 j 是否可以从另一个顶点 i 到达。

这里可达的意思是从顶点i到j有路径。

可达性矩阵称为图的传递闭包。

图以邻接矩阵的形式给出，比如'graph[V][V]'，其中graph[i][j]为1，如果从顶点i到顶点j有一条边，或者i等于j , 否则 graph[i][j] 为 0.

我们可以使用 Floyd Warshall 计算距离矩阵 dist[V][V]，如果 dist[i][j] 是无限的，那么 j 是从 i 不可达的，否则 j 是可达的并且 dist[i] 的值[j] 将小于 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);
}

首先，你能解释一下为什么函数的参数是 graph[][V] 而不是 graph[V][V] 吗？

那为什么我们要初始化矩阵，最终每对顶点之间的距离最短，用graph[V][V]？

你能解释一下初始化之后在 for 循环中做了什么吗？

我们如何编写这个命令:reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]); elsewhise?

编辑:图是否是 bool 矩阵？

如果是这样，那么 reach 不也是一个 bool 矩阵吗？

所以如果我们有这个命令:( reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]); ) 如果 reach [i][j]=1 然后我们执行这个:reach[i][j]=reach[i][j]，否则我们检查是否 (reach[i][k] + reach[k][j] ) 不为零？

还是我理解错了？

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] ?

也可以是图[V][V]。我更喜欢 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]?

那是因为节点a和b之间的距离肯定最多是a和b之间的边的值(假设没有边是无穷大)。 例如:如果我们有图，其中 A 和 B 之间有长度为 5 的边，我们肯定知道 A 和 B 之间肯定存在长度为 5 的路径，但是可能存在更短的路径。

这里有一些重要的事情需要注意。如果您只对可达性感兴趣，那么您并不关心实际距离。在这种情况下，如果不存在任何路径，您可以将值设置为 0，如果存在路径，则设置为 1。

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

您基本上是在使用动态规划方法。说明很长，请在此处阅读: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?

我们可以这样写:reach[i][j] |= (reach[i][k] && reach[k][j])