沃舍尔算法.ppt

考虑考虑n+1个矩阵的序列个矩阵的序列M0,M1,Mn.Mki,j=1当且仅当在当且仅当在R关系图中存在一条从关系图中存在一条从xi到到xj的路径的路径,并且这条路径除端点外中间只经过并且这条路径除端点外中间只经过 x1,x2,.,xk 中的结点中的结点.不难证明不难证明M0是是R的关系矩阵的关系矩阵,而而Mn就对应就对应R的传递包的传递包.沃舍尔算法从沃舍尔算法从M0开始开始,顺序计算顺序计算M1,M2,直到直到Mn为止为止.假设已有假设已有Mk,如何计算如何计算Mk+1?Mk+1i,j=1当且仅当在当且仅当在R的关系图中存在一条的关系图中存在一条xi到到xj,并并且中间只经过且中间只经过 x1,x2,xk,xk+1 的路径的路径.这时可路径分成两种情况这时可路径分成两种情况:uMki,j=1;uMki,k+1=1 且且 Mkk+1,j=1Warshall Warshall 算法算法Warshall 算法输入：M（R的关系矩阵）输出：MT（t(R)的关系矩阵）1.MTM2.for k 1 to n do3.for i 1 to n do4.for j 1 to n do5.MTi,jMTi,j+MTi,k*MTk,j注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加。Warshall 算法 举例例 设A=a,b,c,d，R=,，求t(R)。分析分析 k k1 1 时，时，M MT T i i,jM,jMT T i i,j+M,j+MT T i i,1 1*M*MT T 1 1,j,j M MT T 1 1,jM,jMT T 1 1,j+M,j+MT T 1 1,1 1*M*MT T 1 1,j,j M MT T 2 2,jM,jMT T 2 2,j+M,j+MT T 2 2,1 1*M*MT T 1 1,j ,j 将第将第1 1行加到第行加到第2 2行上行上 M MT T 3 3,jM,jMT T 3 3,j+M,j+MT T 3 3,1 1*M*MT T 1 1,j,j M MT T 4 4,jM,jMT T 4 4,j+M,j+MT T 4 4,1 1*M*MT T 1 1,j,j 得到得到M M1 1。Warshall 算法 举例k k1 1时，第时，第1 1列中只有列中只有MM2 2,1 1 1 1，将第，将第1 1行加到第行加到第2 2行上。行上。k k2 2时，第时，第2 2列中列中MM1 1,2 2 MM2 2,2 2 MM4 4,2 2 1 1，将第，将第2 2行分别加到第行分别加到第1 1,2 2,4 4行上。行上。Warshall Warshall 算法算法 举例举例k k3 3时，第时，第3 3列中列中MM1 1,3 3 MM2 2,3 3 MM4 4,3 3 1 1，将第，将第3 3行分别加到行分别加到第第1 1,2 2,4 4行上。行上。k k4 4时，第时，第4 4列中列中MM1 1,4 4 MM2 2,4 4 MM3 3,4,4MM4 4,4 4 1 1，将第将第4 4行分别加到第行分别加到第1 1,2 2,3 3,4 4行上。行上。此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！