Floyd算法

来自计算思维百科
跳转至: 导航搜索
Floyd算法1.png

如果我们有一张图,图中顶点之间通过边连接,每条边连接的距离有短有长,我们现在想在这张图中找到任意两个点之间的最短距离。Floyd算法就是用于在一个带权图中找到每个顶点到其他所有顶点之间的最短距离。

基本概念

此算法由Robert W. Floyd(罗伯特·弗洛伊德)于1962年发表在“Communications of the ACM”上。同年Stephen Warshall(史蒂芬·沃舍尔)也独立发表了这个算法。Robert W.Floyd在1987年获得了图灵奖。

Floyd算法与Warshall算法及其类似,只不过warshall算法只解决任意两个点之间是否可达的问题,而Floyd算法则是解决任意两点间存在的最短路径的问题。因此Floyd算法就是相当于在warshall算法的基础上添加了权值,以及计算过程中对权值的修改。

应用范围

Floyd算法可以广泛应用于旅行的路径规划、人际关系分析、电缆网络铺设等领域。

使用方法及步骤

  1. 确定顶点和顶点间的关系,写出初始矩阵。
  2. 从矩阵的第一行第一列开始,圈起第一行第一列,寻找其他行列交叉的位置上的值可否由行列上的值替换(更小就替换);
  3. 同2圈起第k行第k列,做同样的替换,一直到矩阵的最后一行最后一列。
  4. 最后得到的矩阵,各个元素对应着对应行到对应列的最短路径。

应用案例

应用1-计划旅程

案例:国庆假期,小明想去4个城市旅游,为了旅程的方便和节省路费,小明事先想知道他想去的4个城市间任意两个城市间的最短路程。

Floyd算法2.jpg

下面是四个城市间的路线图,箭头上的数值表示距离,单位为(10km)

Floyd算法3.png

解决步骤:

1.写出其邻接矩阵R0

Floyd算法4.png

2.用R0表示初始矩阵,用R1 ,R2 ,…, Rk,…, Rn反映依次加入中间节点编号不大于k的路径 。具体使用过程如下:

 将第一行和第一列框起来,看第一行与第一列对应交叉位置上的元素和是否比原值小,若是则替换,如图:

Floyd算法5.png

 被红框框起的部分就是为了寻找各城市能够通过a城市到达其他城市的最短路径,其中被紫框圈住的位置就是可以通过a城市联通的路径,将对应位置的对应在第一行和第一列的元素 相加,即为两城市间通过a城市联通的路径长;5=3+2,9=6+3。

Floyd算法6.png

3.框住第二行第二列在已有路径中再添加b城市,寻找最短路径;

Floyd算法7.png

 c城市到a城市可通过b城市:

Floyd算法8.png

4.框住第三行第三列在已有路径中再添加c城市,寻找最短路径;

Floyd算法9.png

 添加c城市后的路径改变:

Floyd算法10.png

5.框住第四行行第四列在已有路径中再添加d城市,寻找最短路径;

Floyd算法11.png

 添加d城市后,c到a的路径变短了,故修改为6+1=7

Floyd算法12.png

 至此,完全最短路径计算结束。从图中可以看出若小明从任意一个城市出发到其他所有城市的最短路径。

应用2-人际关系亲疏分析

案例:社交网络中,我们的好友和好友的好友,都存在一定的联系,就比如QQ中的亲密度,Floyd算法在社交网络中对用户关系的分析是很重要的,利用Warshall算法可以判断任意两个人是否存在某种联系,而Floyd算法则可以告诉你关系的亲疏度怎么样。例如,有4个人,小A,小B,小C和小D,我们用数值来描述他们之间的关系亲密度,Best Friend的数值为4,好朋友为3,普通朋友为2,熟人为1,不认识为0.那我们就可以使用上面介绍的Floyd方法来绘制一个加权图,从而利用矩阵来算出4个人任意两个人之间的亲密度。

可以体现的计算思维

Floyd算法同Warshall算法类似,都是为了充分利用资源而进行有效的规划,体现了计算思维中的规划思想。