可達矩陣的求解

乘法

第一步：求出自乘矩陣。

第二步：相乘矩陣，乘以相乘矩陣，就是進行布林積（Boolean Product）⊙運算。

第三步：自乘矩陣一直乘下去。

最後：得到的矩陣不再變化時，該矩陣就叫可達矩陣。

冪乘法

第一步：求出自乘矩陣。

第二步：相乘矩陣，乘以相乘矩陣，就是進行布林積（Boolean Product）⊙運算。

第三步：得到的矩陣稱之為冪矩陣，冪矩陣再相乘，一直這樣平方下去。

最後：得到的矩陣不再變化時，該矩陣就叫可達矩陣。

優點：數學表示式簡單，好理解。

缺點：運算慢。矩陣的布林積運算次數多！

另外一個由於冪矩陣中的為1的值相對較多。其實際運算速度不一定就比自乘法快，雖然其，矩陣乘法運算次數相對於自乘法要少！Warshall法

第一步：求出自乘矩陣。

第二步：相乘矩陣，得到轉移矩陣。

第三步：轉移矩陣的相對於自乘矩陣的轉移矩陣，一直迴圈。

最後：得到的矩陣不再變化時，該矩陣就叫可達矩陣。

優點：運算速度中等。

缺點：稍微有點難理解！

改進Warshall法

第一步：求出自乘矩陣。

第二步：相乘矩陣，得到轉移矩陣。

第三步：轉移矩陣的轉移矩陣，一直迴圈。

最後：得到的矩陣不再變化時，該矩陣就叫可達矩陣。

優點：運算速度中等。

缺點：稍微有點難理解！

一次性Warshall法

第一步：根據原始矩陣求出所有的強連通分量

第二步：根據強連通分量得到的是一個良好拓撲排序的矩陣

第三步：從上到下，進行一次Warshall運算就得到了可達矩陣。

優點：運算速度得到數量級的提高。

缺點：難理解！