我发现了以下情况：
给定一个有向图，找出给定图中所有顶点对（i，j）的一个顶点j是否可以从另一个顶点i到达。
这里可达意味着从顶点i到j有一条路径。
可达性矩阵称为图的传递闭包。
该图以邻接矩阵的形式给出，称为“graph[V][V]”，其中，如果从顶点i到顶点j有一条边或i等于j，则graph[i][j]为1，否则graph[i][j]为0。
我们可以用Floyd Warshall计算距离矩阵dist[V][V]，如果dist[i][j]是无穷大的，那么j是不可及的，否则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][v]来初始化矩阵，使每对顶点之间的距离最短？
你能解释一下初始化后在for循环中做了什么吗？
我们怎么写这个命令：
reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);elsewhise？编辑：图形是布尔矩阵，还是不是？
如果是的话，那么不也是布尔矩阵吗？
所以如果我们有这个命令：（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]）是否为非零？
还是我理解错了？
最佳答案
首先，你能解释一下为什么函数的参数是
graph[][v]而不是graph[v][v]？
它也可以是图形我更喜欢graph[v][v]，因为无论如何这是预期的输入。
那么为什么我们要初始化矩阵，最终得到
每对顶点之间的最短距离，用图[v][v]？
这是因为节点a和b之间的距离肯定最多是a和b之间边的值（如果没有边，假设它是无限的）。
如果我们有一个图，在A和B之间有长度为5的边，我们可以肯定地存在长度为5的A和B之间的路径，但是可能存在较短的路径。
这里有一些重要的事情要注意。如果你只对可达性感兴趣，那么你就不在乎实际的距离。在这种情况下，如果不存在任何路径，只要设置路径，就可以将值设置为0，如果存在路径，则可以设置为1。
你能解释一下在初始化之后，在
为了循环？
您基本上是在使用动态编程方法说明很长，请在这里阅读：http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
我们怎么写这个命令：reach[i][j]=reach[i][j]||
（到达[i][k]&&reach[k][j]）；其他？
我们可以写为：reach[i][j]|=（reach[i][k]&&reach[k][j]）