计算邻接矩阵A的k(k<n)次幂,A^k的第i行第j列元素为vi到vj长度为k的路径的条数。C语言实现

可以使用动态规划来求解。定义一个二维数组dp[i][j]表示节点i到节点j的长度为k的路径的数量。那么状态转移方程为：

dp[i][j] = Σ dp[i][u] * A[u][j]

其中，u是节点i和节点j之间的任意一个中间节点。初始状态为dp[i][j] = A[i][j] (当i和j之间有边相连时)和dp[i][j] = 0 (当i和j之间没有边相连时)。

根据状态转移方程，我们可以使用邻接矩阵来实现动态规划。具体实现代码如下：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100

int n; //节点数
int k; //路径长度
int adj[MAXN][MAXN]; //邻接矩阵
int dp[MAXN][MAXN];  //动态规划数组

void matrix_multiply(int a[][MAXN], int b[][MAXN], int c[][MAXN]) {
    //矩阵乘法c=a*b
    int tmp[MAXN][MAXN];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            tmp[i][j] = 0;
            for (int k = 1; k <= n; k++) {
                tmp[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            c[i][j] = tmp[i][j];
        }
    }
}

void matrix_pow(int a[][MAXN], int k, int c[][MAXN]) {
    //矩阵a的k次幂，结果存放在c中
    if (k == 0) {
        //矩阵的0次幂为单位矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    c[i][j] = 1;
                } else {
                    c[i][j] = 0;
                }
            }
        }
    } else if (k % 2 == 1) {
        //k为奇数，先计算a^(k-1)的结果，然后再乘上a
        int tmp[MAXN][MAXN];
        matrix_pow(a, k - 1, tmp);
        matrix_multiply(a, tmp, c);
    } else {
        //k为偶数，计算a^(k/2)的结果，然后再平方
        int tmp[MAXN][MAXN];
        matrix_pow(a, k / 2, tmp);
        matrix_multiply(tmp, tmp, c);
    }
}

int main()
{
    //读入图的信息
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &adj[i][j]);
        }
    }

    //初始化dp数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (adj[i][j]) {
                dp[i][j] = 1; //i和j之间有边相连，路径长度为1
            } else {
                dp[i][j] = 0; //i和j之间没有边相连，路径长度为0
            }
        }
    }

    //动态规划求解
    int tmp[MAXN][MAXN];
    matrix_pow(adj, k, tmp); //计算邻接矩阵的k次幂
    for (int s = 2; s <= k; s++) { //路径长度从2到k
        matrix_multiply(dp, adj, tmp); //计算dp*adj
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = tmp[i][j];
            }
        }
    }

    //输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", dp[i][j]);
        }
        printf("\n");
    }

    return 0;
}