warshell

Warshell 算法 用来求有向图的传递闭包

设R的关系矩阵为M

Mt为在R关系上的传递闭包那么：

Mt = M + M^2 + M^3 +......M^n;

Warshell 算法(时间复杂度O(n^3))

思想：动态规划(记忆式)

用动态规划求关系的传递闭包

#include<iostream>

using namespace std;

bool M[100][100];//布尔数组;

void main()

{

int n;

cout<<"请输入矩阵维数：";

cin>>n;

cout<<"请输入关系矩阵："<<endl;

int i,j,k;

while(n)

{

for(i =1; i <= n; i++)

for(j = 1; j <= n; j++)

cin>>M[i][j];

for(k = 1; k <= n; k++)

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

M[i][j] = M[i][j] + M[i][k]*M[k][j];//布尔数进行的是逻辑加乘;

cout<<"传递闭包："<<endl;

for(i = 1; i <= n; i++)

{

for(j = 1; j <= n; j++)

cout<<M[i][j]<<" ";

cout<<endl;

}

}

}