作者: wjyyy 分类: floyd,图论,最短路,最短路计数,解题报告 发布时间: 2018-07-01 16:21
用floyd解决的最短路计数问题.
在社交网络(social network)的研究中,我们常常使用图论概念去解释一些社会现象.不妨看这样的一个问题.在一个社交圈子里有n个人,人与人之间有不同程度的关系.我 们将这个关系网络对应到一个n个结点的无向图上,两个不同的人若互相认识,则在他们对应的结点之间连接一条无向边,并附上一个正数权值c,c越小,表示两 个人之间的关系越密切.
我们可以用对应结点之间的最短路长度来衡量两个人s和t之间的关系密切程度,注意到最短路径上的其他结点为s和t的联系提供了某种便