algorithm - 带权有向图的邻接矩阵

Question

A) 假设A 是带n 个顶点的加权有向图G 的邻接矩阵，其中A[i,j ] 是边 i 到 j 的权重。如果没有这样的边 A[i ,i]=0。矩阵 A^K= A*A*A*...A。如果我们使用 + 而不是 * 并使用 min 而不是 +，则 Slot A^k [i,j] 不会描述路径 i 的权重到 j 最多有 k 边。我想找这个问题显示什么东西？

B) 假设A 是带n 个顶点的加权有向图(没有循环和多边)G 的邻接矩阵，其中A[i,j] 是边 i 到 j 的权重。如果不存在这样的边 A[i ,j]=infinity，并且对于每条 i 我们有 A[i, i]=0 .矩阵 A^K= A*A*A*...A。 Slot 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]有去j的直接费用来自 i .如您所见result[i, j]是minimum的 result[i, j]和 A[i, k] + A[k, j] , 所以我们得出结论 result[i, j]包含从 i .. j 开始的路径使用一个中间顶点 k .由于我们对所有 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脚步。你可以做的是初始化 A[i, j]作为1如果我们在 i 之间有一条边和 j否则 0 .

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