我的快乐小窝 龙井产地 弗洛伊德(Floyd)算法详解

弗洛伊德(Floyd)算法详解

Floyd 算法是解决图论问题的比较经典的算法,用来求解赋权图中每对顶点间的最短距离。当然,在求距离的过程中也可以得到最短距离的路径。这个算法与迪杰斯特拉(Dijkstra)算法相似,他们两个都属于最短路算法,只是Dijkstra算法更适合求图中给定两点的最短距离和路径,求每对顶点之间的距离计算量比较大。不过个人觉得Dijkstra算法更复杂一些,对入门的同学不是很友好。而Floyd 算法相对比较简单,算法容易实现,比较适合入门。

在讲算法之前,兔兔先介绍一下本文用到的图论的相关基础知识。

 基础知识

首先是图的表示方法。一般情况下分为关联矩阵、邻接矩阵、邻接表等。其中比较常用的是邻接矩阵,本文先对邻接矩阵做讲解。其次的图的类型。图的类型的非常多的,为了区分比较,本文先介绍相关的4种:无向非赋权图(G),有向非赋权图(D),无向赋权图(G),有向赋权图(D)。关于图论的其它详细知识,兔兔之后会单独在其它文章进行讲解。

对于图,我们可以根据图里面是否有方向(箭头)分为有向图和无向图。有向图,顾名思义就是里面有箭头表示方向,而且只能沿着箭头的方向行走,逆箭头方向就是不能走的,有向图用D表示;无向图,就是双向联通的,没有箭头,在图上用直线连接,通常用G表示。赋权图就是连接两个节点之间的线是有长度的,有具体的数值。非赋权图就是没有长度的要求,更确切的说,就是认为所有长度都用1表示。

上面的红色是节点,因为有箭头方向,所以是有向图。因为每条线上没有权值,也就是非赋权图。所以可以称为:有向非赋权图。

 上面的图就是一个无向图,两个相邻节点是双通的。由于边上有权值,就说明是有长度距离的。比如从1走到2或从2走到1,距离就是3。

在解决最短路问题中,我们遇到的通常是无向赋权图。然后求最短路径。对于上面的图。比如说从3走到2,可以走3->1->2这条路,距离是4+3=7;也可以走3->4->1->2,距离就是3+2+3=8。那么最短路径就是走3->1->2。

求最短路径,我们需要把图转化成数学语言再进行操作,邻接矩阵就是这样的东西。比如上面4个节点1,2,3,4。我们把一个二维矩阵每一个行代表一个节点。第一行是节点1,第二行节点2......然后每一列也代表一个节点,第一列节点1,第二列节点2......这样第i行第j列就代表节点i与节点j之间的距离,也就是权值。如果两个节点之间没有连线(在无向图中),或是在有向图中没有从i指向j的箭头,那就用0或无穷符号表示。在赋权图中矩阵上对应的值是权值,那么在非赋权图中就用0,1表示:1代表连接,0代表没有连接通路。对于对角线元素,就是自己和自己,用0表示。

那么,对于第一个图,邻接矩阵就是:

0111
0000
0001
1000

第二个图,邻接矩阵如下:

  

0342
3000
4003
2030

不难发现,无向图的邻接矩阵是对称阵。

算法原理

Floyd算法是经典的动态规划算法,基本思想是递推产生一个矩阵序列A1,A2,.....,Ak,...,An(图有n个节点),Ak=(ak(i,j))nxn。其中矩阵Ak第i行第j列表示从顶点vi到顶点vj的路径上经过的顶点序号不大于k的最短路径长度。

迭代公式a_{k}(i,j)=min(a_{k-1}(i,j),a_{k-1}(i,k)+a_{k-1}(k,j))

k是迭代次数,i,j,k=1,2......n。

当最后k=n是时,An矩阵就是各个顶点之间的最短距离值了。

那么如果需要记录路径,那么需要引入路由矩阵。路由矩阵Rk=(rk(i,j))nxn,用来记录两点之间路径的前驱后继的关系,其中rk(i,j)表示从顶点vi到顶点vj的路径经过编号为rk(i,j)的顶点。所以需要注意了,路由矩阵里面不是数值,而是结点。

以上理论听起来挺复杂的。不过没有关系的。真正的算法实现无外乎就是三个循环嵌套,i,j的循环是任意两个点,而k则是两个点之间所经过的第三个点,我们就是在循环之中不断比较从i到j的距离与从i到k距离加上从k到j距离的大小,如果经过这个点,路径变短了,我们就接受这个点,认为可以经过这个点;否则就不经过这个点,就是从i到j最短。

如果我们得到的路由矩阵,那怎样得到路径呢?我们得到的路由矩阵Rn,其中r(i,j)(就是路由矩阵第i行j列)表示第i个节点到第j个节点最短路径经过的中间点p1。那么我们先向起始顶点vi反向追踪,得到r(i,p1)=p2,r(i,p2)=p3...,最终r(i,pn)=0,就结束了;再正向追踪,r(p1,j)=q1,r(q1,j)=q2.....r(qt,j)=0,完成正向追踪。路径就是vi,pn,...p2,p1,q1,q2...qt,vj。

算法实现

我们以一个例子来进行算法实现:

import numpy as np
A=np.mat([[0,3,0,2,0],
   [3,0,2,1,0],
   [0,2,0,0,5],
   [2,1,0,0,4],
   [0,0,5,4,0]]) #邻接矩阵
G=nx.Graph(A) #无向赋权图
pos=nx.shell_layout(G) #布局设置
w=nx.get_edge_attributes(G,"weight") #获取权重
nx.draw_networkx(G=G,pos=pos,node_size=260) #画网络图
nx.draw_networkx_edge_labels(G=G,pos=pos,font_size=12,edge_labels=w) #标注权重
plt.show()

矩阵如下所示:

 算法代码如下:

import numpy as np
from numpy import inf
A=[[inf,3,inf,2,inf],
   [3,inf,2,1,inf],
   [inf,2,inf,inf,5],
   [2,1,inf,inf,4],
   [inf,inf,5,4,inf]]
dis=A #邻接矩阵包含了任意两个节点之间的距离,distance
path=np.zeros((n,n)) #初始化路由矩阵,让它都是零
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dis[i][k]+dis[k][j]<dis[i][j]:
                dis[i][j]=dis[i][k]+dis[j][k] #找到经过k点时路径更短,接受这个更短的路径长度
                path[i][j]=k #路由矩阵记录路径
print(dis) #显示每对顶点最短路径长度
print(path) #显示路由矩阵

为什么这里用inf呢?之前说了,如果两点没有连接或是同一个节点,可以用0或正无穷表示。但是在计算该算法时,如果用零的话,计算过程肯定认为 0 是最短路径,这样我们最终得到的最短路径距离矩阵就是全零矩阵了。所以一定要用inf来表示没有连接的两个节点

运行结果如下:

dis=[[4, 3, 5, 2, 6], 
    [3, 2, 2, 1, 5], 
    [5, 2, 4, 3, 5], 
    [2, 1, 3, 2, 4], 
    [6, 5, 5, 4, 8]] #距离矩阵

path=[[3. 0. 1. 0. 3.]
     [0. 3. 0. 0. 3.]
     [1. 0. 1. 1. 0.]
     [0. 0. 1. 1. 0.]
     [3. 3. 0. 0. 3.]] #路由矩阵

我们以0到4 点为例,最短距离是6。path[0][4]=3,该路径经过点3,反向追踪:path[0][3]=0,结束;正向追踪:path[3][4]=0,结束。最短路径就是0->3->4。看一看前面的图,的确符合事实。

但是,实际上,这五个点最好用a,b,c,d,e等表示,或是1,2,3,4,5。这里的用做终止追踪的0其实是初始时的0,而这个矩阵当中也有作为节点标记的0,看的时候很容易混淆。如果我们用字母标记,最终会看到路由矩阵中有节点标记,也有数字0,看起来会方便很大的。

总结

弗洛伊德算法的算法实现比较简单,过程容易理解,但原理不是很容易消化透彻。同学们在学习的时候可以根据算法过程,找一个具体的图仔细捋一捋,画一下距离矩阵与路由矩阵变化过程,以及当中第三点的选取、距离的比较等,体会当中的动态规划思想。该算法可以求最短路径及其长度,但是对于复杂的网络,该算法还是有局限性的。这个时候我们便需要选择其它的自然算法,例如蚁群算法等来进行求解。虽然那些相对“高级”的算法不一定在众多的路径中找到最短的那一条,但是却可以在较短时间内找到比较短的一条路径,而且会很接近最短路径的。