Warshall算法的matlab实现（计算传递闭包）

Warshall算法步骤

1. 置新矩阵A:=M;
2. 置i:=1;
3. 对所有j，如果A[j,i]=1，则对k=1,2,…,n，有A[j,i]:=A[j,k]+A[i,k];
4. i加1；
5. 如果i<=n,则转到步骤（3），否则停止。

实例

设A={a,b,c,d}，给定A上的关系R为R={<a,b>,<b,a>,<b,c>,<c,d>}，求t®。

1. i=1时，第一列中只有A[2,1]=1，将第二行与第一行各对应元素进行逻辑相加，仍记于第二行。
   
2. i=2时，第二列中A[1,2]=A[2,2]=1，分别将第一行、第二行各对应元素和第二行进行逻辑相加，仍分别记于第一行、第二行。
   
3. i=3时，第三列中A[1,3]=A[2,3]=1，分别将第一行、第二行各对应元素和第三行进行逻辑相加，仍分别记于第一行、第二行。
   
4. i=4时，第四列中只有A[3,4]=1，将第三行与第四行各对应元素进行逻辑相加，仍记于第三行。
   

matlab实现

function R=warshall(A)
n=size(A,1);
R=A;
for i=1:n
for j=1:n
if (R(j,i)==1)
for k=1:n
R(j,k)=logical(R(j,k)+R(i,k))
end
end
end
end

实例验证

在给出有向图，得出邻接矩阵后，也可以通过Warshall算法求出可达性矩阵。（可达性矩阵可用上述matlab程序）