赋权有向图的邻接矩阵

Question

A)设A是具有n个顶点的赋权有向图G的邻接矩阵，其中A[i,j]是边i到j的权重。如果没有这样的边缘A[i ,i]=0。矩阵A^K= A*A*A*...A。如果我们使用+而不是*，并且使用min而不是+，则时隙A^k [i,j]不能用至多k边来描述路径i到j的权重。我想找出这个问题表现出什么东西？

B)设A是具有n点的赋权有向图(无圈多边) G的邻接矩阵，其中A[i,j]是边i到j的权重。如果没有这样的边缘A[i ,j]=infinity，并且对于每个i，我们都有A[i, i]=0。矩阵A^K= A*A*A*...A。老虎机A^k [i,j]展示什么东西？最小重量？或者...？

有什么想法吗？

编辑:我的意思是这些算法在图中找到了哪一个？找到最大重量？最小重量？什么也没找到？

Answer 1

让B = A^K

B[i, j]将表示到i .. j的最短路径，该路径恰好采用k步骤。怎么做到的？

给定一个矩阵A，如果我们使用多个A本身，会发生什么？

    // Initialize a matrix result which would be the matrix obtained by A*A
    vector< N, vector<int> (N, INF) > result;
    REP(i,0,N) REP(j,0,N) REP(k,0,N)
        result[i][j] = min(result[i][j], (A[i][k] + A[k][j]));

最初，A[i, j]有从i转到j的直接成本。正如您所看到的，result[i, j]是result[i, j]和A[i, k] + A[k, j]的minimum，因此我们得出结论，result[i, j]包含使用一个中间顶点k从i .. j出发的路径。由于我们对所有k's都进行了迭代，因此result[i, j]包含恰好遍历两条边的最小成本路径。我们现在可以对A^k进行泛化。

如果我们将A[i, i]设置为0会怎么样？

这允许自循环。在上面的代码中，当k == i时，

    result[i, j] = min(result[i,j], A[i, i] + A[i, j])
    result[i, j] = min(result[i,j], A[i,j)] // since A[i, i] = 0;

这意味着，如果我们可以使用一条或两条边，现在result[i, j]将表示从i .. j到达的最短路径。

因此，现在B[i, j]将表示到i .. j的最短路径，几乎需要k个步骤。

类似地，我们可以使用相同的概念来计算来自i .. j的恰好采用k步骤的路径数。您可以做的是，如果我们在i和j之间有一个优势，那么将A[i, j]初始化为1，否则就是0。

A^k会给你想要的结果。