floyd算法.ppt

《floyd算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、六度分离hdu1869ProblemDescription1967年，美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(smallworldphenomenon)”的著名假说，大意是说，任何2个素不相识的人中间最多只隔着6个人，即只用6个人就可以将他们联系在一起，因此他的理论也被称为“六度分离”理论(sixdegreesofseparation)。虽然米尔格兰姆的理论屡屡应验，一直也有很多社会学家对其兴趣浓厚，但是在30多年的时间里，它从来就没有得到过严谨的证明，只是一种带有传奇色彩的假说而已。Lele对这个理论相当有兴趣，于是，

2、他在HDU里对N个人展开了调查。他已经得到了他们之间的相识关系，现在就请你帮他验证一下“六度分离”是否成立吧。Input本题目包含多组测试，请处理到文件结束。对于每组测试，第一行包含两个整数N,M(0

3、eInput8701122334455667880112233445566770SampleOutputYesYes每一对顶点间的最短路径Dijkstra算法是求源点到其它顶点的最短路径。怎样求任意两个顶点之间的最短路径？我们可以把Dijkstra算执行n次，每次从不同的顶点开始，则算法时间复杂度为O（n3）。Floyd弗洛伊德给出了另一个算法，时间复杂度也是O（n3），但是形式上简单些。从演示中看算法思想一个简单的图及其邻接矩阵如下：abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca

4、,3)(cb,∞)(cc,0)D(-1)从上面的D（-1）开始，对于每两个顶点u、v，在D（-1）中存储着一条路径u…v。现在我们考察，试着把a加到u、v的路径上能否，得到一条更短的路径，即如果u…a+a…v

5、也不必考虑abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)c(ca,3)(cc,0)D(0)D[b][a]+D[a][c]=6+11>D[b][c]=2，所以如果从a绕，反而远，那么这一项不变。abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)

6、(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cc,0)D(0)abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cc,0)D(0)D[c][a]+D[a][b]=3+4

7、)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)从上面的D（0）开始，对于每两个顶点u、v，在D（0）中存储着一条路径u…v。现在我们考察，试着把b加到u、v的路径上能否，得到一条更短的路径，即如果u…b+b…v

8、1)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)本来路径上源点或终点就有b的不必考虑。对角线上的也不必考虑a