Floyd-Warshall算法描述 1)适用范围: a)APSP(All Pairs Shortest Paths) b)稠密图效果最佳 c)边权可正可负 2)算法描述: a)初始化:dis[u,v]=w[u,v] b)For k:=1 to n For i:=1 to n For j:=1 to n If dis[i,j]>dis[i,k]+dis[k,j] Then Dis[I,j]:=dis[I,k]+dis[k,j] c)算法结束:dis即为所有点对的最短路径矩阵 3)算法小结:此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法。时间复杂度O(n^3)。 考虑下列变形:如(I,j)∈E则dis[I,j]初始为1,else初始为0,这样的Floyd算法最后的最短路径矩阵即成为一个判断I,j是否有通路的矩阵。更简单的,我们可以把dis设成boolean类型,则每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”来代替算法描述中的蓝色部分,可以更直观地得到I,j的连通情况。
标签: Floyd-Warshall Shortest Pairs Paths
上传时间: 2013-12-01
上传用户:dyctj
1. Matrix-chain product. The following are some instances a) <3, 5, 2, 1,10> b) <2, 7, 3, 6, 10> c) <10, 3, 15, 12, 7, 2> d) <7, 2, 4, 15, 20, 5>
标签: Matrix-chain following instances product
上传时间: 2014-11-28
上传用户:731140412
该系统主要实现简单的大学学生选修课程的功能。 1.系统的用户主要分为2类:学生和管理员 2.数据描述 <1> 课程: 课程号、课程名、学分、学时、教师、开课学期、适用专业、最大选课人数 <2> 学生:学号、姓名、密码、专业年级 <3> 学生选课情况:学号、课程号、是否已经考试、成绩 <4> 管理员:编号、姓名、密码 3.功能描述 <1> 学生功能: a. 登录:学生使用学号和密码登录。 b. 选课功能:学生能够选择所需要的课程。 c. 退选功能:学生能够退选课程。 d. 选课情况查询:查询该学生已经选的课程(分学期)。 e. 成绩查询:查询该学生某一门课程的成绩,某学期所有课程的成绩。 <2> 管理员功能 a. 登录: b. 管理课程:包括课程的增加、删除、修改等。 c. 选课管理:能够列出指定学期、课程的选课学生名单,能够对学生的选课进行调整。 d. 成绩表管理:能够录入学生的成绩,列出指定学期、课程的成绩单。
上传时间: 2016-03-06
上传用户:jyycc
java写的围棋游戏小程序 开发思路 调用applet类作为父类。在init事件中调用Qipan类,作出panel,上加控制用控件。在paint事件里调用drawline函数画棋盘,注册鼠标动作。鼠标单击位置上用drawoval画出棋子, 事件处理过程 A。重新开始 B。选择尺寸 C。悔棋事件 D。前进事件 有三个文件Weiqi.java,Qizi.java,Qipan.java
上传时间: 2014-01-07
上传用户:gyq
QTP全名Quick Test Professional,是MI公司出品的一款测试工具.它的优点是使用方便,功能强大并且可以通过与测试管理工具的互连达到自动化功能测试的目的. QTP是专门针对B/S模式的测试工具.它具有:识别能力强,回放精确等优点,是进行B/S模式下功能测试的首选工具
标签: Professional QTP Quick Test
上传时间: 2016-04-21
上传用户:tyler
费诺编码的步骤: A 将概率按从大到小的顺序排列 B 按编码进制数将概率分组,使每组概率和尽可能接近或相等。 C 给每组分配一位码元 D 将每一分组再按同样原则划分,重复b和c,直到概率不再可分为止
上传时间: 2016-06-24
上传用户:xinyuzhiqiwuwu
、该个词法分析器要求至少能够识别以下几类单词: a. 关键字:else if int return void while共6个,所有的关键字都是保留字,并且必须是小写; b. 标识符:识别与C语言词法规定相一致的标识符,通过下列正则表达式定义:ID = letter (letter | digit)*; c. 常数:NUM=(+ | - |ε)digit digit*(.digit digit* |ε)(e(+ | - |ε) digit digit* |ε),letter = a|..|z|A|..|Z|,digit = 0|..|9,包括整数,如123, -123, +123等;小数,如123.45, +123.45, -123.45;科学计数法表示的常数,如+1.23e3,-2.3e-9; d. 专用符号:+ - * / < <= > >= == != = , ( ) [ ] { } /* */;
上传时间: 2013-12-08
上传用户:gtf1207
标准化考试系统 (B/S网络版) 用JAVA编写的考试系统,是JAVA课程设计时的作品! 客户端主类ClientBS 客户端选择试题界面ChoiceFile 客户端考试界面ClientTestArea 服务器端主类Server 服务器端读取试题 ReadTestquestion
上传时间: 2013-12-26
上传用户:yyyyyyyyyy
DESCRIPTION : BIN to seven segments converter -- segment encoding -- a -- +---+ -- f | | b -- +---+ <- g -- e | | c -- +---+ -- d -- Enable (EN) active : high -- Outputs (data_out) active : low
标签: DESCRIPTION converter segments encoding
上传时间: 2016-08-17
上传用户:ainimao
这是一个三次样条插值的.m程序 输入的是一个二维数组A(Nx2) 插值方法为: S(x) = A(J) + B(J)*( x - x(J) ) + C(J)*( x - x(J) )**2 +D(J) * ( x - x(J) )**3 for x(J) <= x < x(J + 1)
上传时间: 2013-12-14
上传用户:gengxiaochao