加权有向图的邻接矩阵

Question

B）设a是带有向图（无环多边）G的一个邻接矩阵，其中a[i,j]是边i到j的一个权重。如果没有这样的边a[i,j]=infinity并且对于evreyi我们有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]));

    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;

所以现在b[i,j]将表示从i开始的最短路径。j几乎需要k步骤。

类似地，我们可以使用相同的概念从i计算路径的no。J执行的步骤正好为K。如果在i和j之间有边，则可以将a[i,j]初始化为1，否则0。

|^K将提供所需的结果。