可达矩阵到缩减矩阵
如何用EXCEL计算可达矩？
可达矩阵怎么算？
可达矩阵的求解乘法第一步：求出自乘矩阵。第二步：相乘矩阵，乘以相乘矩阵，就是进行布尔积（Boolean Product）⊙运算。第三步：自乘矩阵一直乘下去。最后：得到的矩阵不再变化时，该矩阵就叫可达矩阵。幂乘法第一步：求出自乘矩阵。第二步：相乘矩阵，乘以相乘矩阵，就是进行布尔积（Boolean Product）⊙运算。第三步：得到的矩阵称之为幂矩阵，幂矩阵再相乘，一直这样平方下去。最后：得到的矩阵不再变化时，该矩阵就叫可达矩阵。优点：数学表达式简单，好理解。缺点：运算慢。矩阵的布尔积运算次数多！另外一个由于幂矩阵中的为1的值相对较多。其实际运算速度不一定就比自乘法快，虽然其，矩阵乘法运算次数相对于自乘法要少！Warshall法第一步：求出自乘矩阵。第二步：相乘矩阵，得到转移矩阵。第三步：转移矩阵的相对于自乘矩阵的转移矩阵，一直循环。最后：得到的矩阵不再变化时，该矩阵就叫可达矩阵。优点：运算速度中等。缺点：稍微有点难理解！改进Warshall法第一步：求出自乘矩阵。第二步：相乘矩阵，得到转移矩阵。第三步：转移矩阵的转移矩阵，一直循环。最后：得到的矩阵不再变化时，该矩阵就叫可达矩阵。优点：运算速度中等。缺点：稍微有点难理解！一次性Warshall法第一步：根据原始矩阵求出所有的强连通分量第二步：根据强连通分量得到的是一个良好拓扑排序的矩阵第三步：从上到下，进行一次Warshall运算就得到了可达矩阵。优点：运算速度得到数量级的提高。缺点：难理解！
可达矩阵的三种求法？
1.
连乘法：其中A为原始邻接布尔矩阵，I为单位矩阵，R为可达矩阵。
2.
幂乘法：
3.
warshall算法：通过转移矩阵的方式计算出可达矩阵。
4.
迭代warshall算法：对每个要素进行warshall操作后，记录其状态，下个要素迭代时候是以当前状态为基础进行迭代。