warshell

编辑:中用网互动百科 时间:2020-03-30 05:36:12
编辑 锁定
本词条缺少概述名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
中文名
warshell
矩    阵
设R的关系矩阵为M
算    法
用来求有向图的传递闭包
思    想
动态规划(记忆式)
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;
}
}
}
词条标签:
理学