基于Floyd算法的大型停车场导航系统的设计

高振，陈顺龙，王珏辉

（长江大学工程技术学院，湖北荆州，434000）

0 引言

“停车难”加重交通拥堵。在北京中关村、南京新街口、广州天河等繁华商圈，车位的捉襟见肘造成了交通的严重拥堵。“停车难”引发公共纠纷。把Floyd算法应用在大型停车导航系统的设计，在一定程度上，能够解决“停车难”的问题。

1 Floyd算法的原理分析

通过Floyd计算图D=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

图1 图转化矩阵

图2 初始矩阵转化最短路径矩阵

假设图D中顶点个数为N，则需要对矩阵S进行N次更新。初始时，矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。接下来开始，对矩阵S进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”。同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k]+a[k][j]”，则更新 a[i][j]为”a[i][k]+a[k][j]”。更新N次之后，操作完成！

2 探求Floyd算法的动态规划本质

从表面上粗看，Floyd算法是一个非常简单的三重循环，而且纯粹的Floyd算法的循环体内的语句也十分简洁。正是由于“Floyd算法是一种动态规划（Dynamic Programming）算法”的本质，才导致了Floyd算法如此精妙。因此，这里将从Floyd算法的状态定义、动态转移方程以及滚动数组等重要方面，来简单剖析一下图论中这一重要的基于动态规划的算法——Floyd算法。

在动态规划算法中，处于首要位置、且也是核心理念之一的就是状态的定义。在这里，把d[k][i][j]定义成：“只能使用第1号到第k号点作为中间媒介时，点i到点j之间的最短路径长度。”

图中共有n个点，标号从1开始到n。因此，在这里，k可以认为是动态规划算法在进行时的一种层次，或者称为“松弛操作”。d[1][i][j]表示只使用1号点作为中间媒介时，点i到点j之间的最短路径长度；d[2][i][j]表示使用1号点到2号点中的所有点作为中间媒介时，点i到点j之间的最短路径长度；d[n-1][i][j]表示使用1号点到(n-1)号点中的所有点作为中间媒介时，点i到点j之间的最短路径长度d[n][i][j]表示使用1号到n号点时，点i到点j之间的最短路径长度。有了状态的定义之后，就可以根据动态规划思想来构建动态转移方程。

动态转移的基本思想可以认为是建立起某一状态和之前状态的一种转移表示。按照前面的定义，d[k][i][j]是一种使用1号到k号点的状态，可以想办法把这个状态通过动态转移，规约到使用1号到(k-1)号的状态，即d[k-1][i][j]。对于d[k][i][j]（即使用1号到k号点中的所有点作为中间媒介时，i和j之间的最短路径），可以分为两种情况：（1）i到j的最短路不经过k；（2）i到j的最短路经过了k。不经过点k的最短路情况下，d[k][i][j]=d[k-1][i][j]。经过点k的最短路情况下，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。因此，综合上述两种情况，便可以得到Floyd算法的动态转移方程：

d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])（k,i,j ∈ [1,n]）

3 大型停车导航系统应用分析

在大型停车导航系统中，会将所有的停车位录入到数据库中，系统会将数据库的停车位构造成初始矩阵，利用Floyd算法将计算出最短路径。根据车主提供的所在地址和目的地址，返回号航路线，能够提供一种高效地寻找停车位的方式。

参考文献

[1]许克平,曾明月,鄢好,袁丽娟,彭圆红.基于不确定因素下的Floyd算法改进[J]. 中国科技信息. 2016(18).

[2]叶奇明,石世光Floyd算法的演示模型研究[J].海南大学学报(自然科学版). 2008(01).

[3]曹睿.基于Floyd算法的最短路径问题应用研究[J].内江科技. 2012(08).

[4]魏霖静,岳建斌. Floyd算法在一类实际问题中的应用[J].电脑知识与技术. 2010(22).