Question

请问谁能用简单易懂的语言介绍一下warshall算法.离散数学完全不知道老师讲了什么.如果能举一个关系矩阵的例子就更好了

Answer 1

Warshall在1962年提出了一个求关系的传递闭包的有效算法.其具体过程如下,设在n个元素的有限集上关系R的关系矩阵为M：

（1）置新矩阵A=M;

（2）置k=1;

（3）对所有i如果A[i,k]=1,则对j=1..n执行：

A[i,j]←A[i,j]∨A[k,j];

（4）k增1;

（5）如果k≤n,则转到步骤（3）,否则停止.

所得的矩阵A即为关系R的传递闭包t(R)的关系矩阵.

如果你认可我的回答,敬请及时采纳,

祝你学习进步,更上一层楼! (*^__^*)