一:Warshall算法的定义: 有向图的传递闭包
一个n顶点有向图的传递闭包可以定义为一个n阶布尔矩阵,
T {tij}如果顶点i到顶点j存在一条有效路径,则tij 1,否则tij 0。
eg:
二:Warshall算法思想 划分阶段
用n阶布尔矩阵R(k)(0≤k ≤n)来表示有向图中任意一对节点是否有有向路径的信息。
因此,可将原问题划分为如下的决策阶段: R(0),…, R(k-1), R(k),…, R(n) R(0)就只是有向图的邻接矩阵。
R(1)包含可以用第一个顶点作为中间点的路径信息。
R(n)说明可以用所有的顶点作为中间点寻找有向路径,所以R(n)就是我们要求的传递闭包。
这个算法的中心是我们可以通过R(k-1)来计算R(k)的所有元素。 递推关系式

1104040216 日期:2013/9/14 班级:信管 112 学号: 1104040216 姓名:庞贝贝 同组...D(C ) ? (C ? k ) mod(26) 2、使用 c++语言实现凯撒密码算法 2.1....
信息安全原理与应用 实验报告二单表代换密码 姓名:庞贝贝 班级:信管 112 指导老师:周一鹏 学号:1104040216 日期:2013/9/15 班级:信管 112 学号: 110404...
庞贝贝-1104040216-课设报告7-图的建立与遍历_军事/政治_人文社科_专业资料。... warshall算法-信管112-庞... 暂无评价 4页 免费喜欢此文档的还喜欢 无向图...
试验报告八 课题名称 订票系统 班级:信管 112 姓名:庞贝贝 学号:1104040216 日期:2013/7/17 1 一、需求分析 1、任务通过此系统可以实现如下功能 1、录入: ...
试验报告八 课题名称 订票系统 班级:信管 112 姓名:庞贝贝 学号:1104040216 日期:2013/7/17 1 一、需求分析 1、任务通过此系统可以实现如下功能 1、录入: ...
热门文档