王 飞，袁 涛，王 蒙

(安徽机电职业技术学院，安徽 芜湖 241002)

图(Graph)是一种非线性结构，由顶点和边组成，顶点表示图中的数据元素，边表示数据元素之间的关系.图可定义为G=(V，E),其中V是顶点的非空有穷集合，E是用顶点对表示边的有穷集合；按照图中表示边的顶点对是否有序可以把图分为有向图和无向图；具有n个顶点的无向图，其边的数量如果达到了n*(n-1)/2,或是具有n个顶点有向图，边的数量达到了n*(n-1)，则称该图为完全图；在一个无向图中任意两个顶点Vi和Vj都有路径相通，则该图称为连通图，在一个有向图中任意两个顶点Vi和Vj都有路径相通，则该图称为强连通图.图的每条边或弧上若有一个具有一定意义的数值，该数值称为权，边或弧上带权的连通图称为网.图的存储方式有两种:邻接矩阵和邻接表.

在图中经典的算法有求最小生成树的普里姆算法和克鲁斯卡尔算法；在带权图中求最短路径算法有经典的Dijkstra算法和Floyd算法等.

图论算法在计算机科学中扮演着很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式.很多问题都可以转化为图论问题，然后用图论的基本算法加以解决.在研究各类算法并根据所针对的具体问题对其进行改进的工作中，有一个前提工作就是要根据不同要求来进行构建各类图或者网，在算法的一次实现中，可以通过构造静态图或者静态网，但是在对算法的研究中，需要多次构造不同的图并在该图上验证算法，这个时候就需要动态随机地生成多个符合要求的图或网供算法的实现和验证使用.

1 联通网的随机生思路与最短路径算法的简介

1.1 联通网的随机生思路

在图论中的一些重要的方法如图的遍历算法、最短路径算法、最小生成树算法等都是建立在有图或者是网的基础上的.而图的产生一般是有两种办法实现，一种是提前设定参数来生成图，这种方法的优点在于参数信息可控，可以预先准备大量的数据来产生丰富的图；缺点也是明显的，就是在准备参数过程中比较费时费力，而且产生的图的参数具有一定局限性，不利于对系统的综合测试及验证.另一种方法就是随机产生法，具体来说就是随机产生图的顶点个数、图的边的个数以及边的权值.这种图的生成法的优点和缺点也是显而易见的：优点是产生图的效率比较高，可以随机快速地产生参数、类型丰富的图或者网；效率比较高，也有利于对系统的综合测试及验证；缺点也较为明显：由于是随机产生图的参数来构建图，较容易产生一些不符合实际需要或逻辑错误的图，这对于在图上研究相关问题是有着重大不利影响.

鉴于以上分析，本文提出的方法结合两种方法的优缺点，将两种方法的优点结合起来.总体来说,还是通过随机生成的方法来生成所需要的图或者是网，对于可能产生错误逻辑的图或者网，我们采用的方法是在综合考虑现实研究问题对应的图或者是网参数的合理范围，对随机生成图的参数范围进行合理限定，这样既能快速高效地产生图或网，又能避免产生参数不合理图或网对所研究的问题产生负面影响.

1.2 最短路径的基本概念及算法分析

作为图论的经典问题，最短路径一直是一个在工程规划、地理信息系统、军事等领域应用十分广泛的问题，对该问题的研究有着重要的理论和应用价值.最短路径度量标准不仅是空间距离上的，还可以为时间、花费代价等其他的度量标准[1].根据度量标准的不同，最短路径问题可以转换为耗时最短、花费最低等问题.网络分析中最基本、关键的问题是最短路径问题[3]；无论是距离最短、耗时最短还是花费最低，其核心都是最短路径算法.随着图论的相关算法不断更新发展，解决最短路径问题算法针对不同的图网特征、应用需求等方面不断推陈出新，在时空复杂度、易于实现等方面特色各异[2].

简单来说，从图中的一个顶点到另一顶点如果存在相通的路径，找到一条路径使得沿此路径上所有边的权值最小的问题就是最短路径问题.目前理论上最完善、得到广泛的普及和应用的最短路径算法是采用贪心的启发策略的Dijkstra算法[4，5].最短路径算法有标号算法和代数算法两大类，Dijkstra算法属于标号算法的一种，标号算法的代表除Dijkstra算法外还有Floyd算法[6，7].Dijkstra算法性能稳定，较能适应网络拓扑变化，主要针对研究单一起点的最短路径问题，易实现且通用性强[3,8]；该算法时间复杂度为O(n2)，适用于网络节点较少的情况下[3].Floyd算法主要研究网络中两点间的最短路径，时间复杂度为O(n3).

本文研究的背景问题是为公路网中行驶的电动汽车寻找最佳充电点设计算法，这个问题可以从两个方面考虑，一方面从独立行使的电动汽车自身来说可以理解为这是单一起点的最短路径设计算法，当前电动汽车所在位置就是起点；另一方面，考虑到车联网技术的长足发展，很多行驶中的电动汽车的服务请求都可以通过网络服务中心得到解决，而网络服务中心面临的很多问题是要同时解决很多网络节点发来的类似请求.公路网中行驶的电动汽车寻找最佳充电点的问题，可能在同一时刻在某个区域内多辆汽车都需要找到充电节点进行充电，可以考虑在网络服务中心执行Floyd算法同时求出区域中每个节点的最佳充电服务点；当然针对具体问题还需要对Floyd算法进行改进以更加高效地解决问题，这样做比单一起点的最短路径算法要更加全面高效.

1.3 Floyd算法的思想

设一有向网络G=(V,E)，求V集合中各点到其余各顶点的最短距离，通过Floyd算法来解决这个问题需要引入两个矩阵S、P，S中的元素s[i][j]表示顶点i到顶点j的距离权值.矩阵P中的元素p[i][j]，表示顶点i到顶点j经过了p[i][j]记录的值所表示的顶点.假设图G中顶点个数为N，则需要对矩阵S和矩阵P进行N次更新.初始时，矩阵S中顶点s[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则s[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值.

具体算法描述为(算法1：Floyd算法)：

Step1：初始化矩阵S和P；使得S中的元素s[i][j]表示顶点i到顶点j的距离权值，即s[i][j]=wij.矩阵P中的元素p[i][j]，表示顶点i到顶点j经过了p[i][j]记录的值所表示的顶点，初始时p[i][j]=j;

Step2：For k:=1 to N

For i:=1 to N

For j:=1 to N

If s[i][j]>s[i][k]+s[k][j]

Then {s[i][j]:=s[i][k]+s[k][j];p[i][j]=p[i][k];}

Step3：算法结束，矩阵S存储所有点对之间的最短路径长度，矩阵P存储所有点对的最短路径信息.

2 改进Floyd算法在随机生成网上的实现

2.1 问题背景分析

在当前各大城市中充电汽车日益普及的情况下，行驶中电动汽车在电量不足时寻找合适充电桩进行充电的问题是本文所研究问题的大背景.该问题其实就是最短路径问题，利用Floyd算法找到路网中各点之间的最短路径，考虑到路网中并不是每一个点都是充电节点，而充电点中每个充点电可能存在其他电动汽车正在占用、排队等待的情况，解决这样的问题需要对Floyd算法进行改进形成符合解决问题所需要的算法，改进的思想就是把充电点中等待充电的汽车数量与当前行驶速度、每辆汽车充电所需时间等相关参数利用公式1折算成其余各点到达该点距离的一部分，具体如下：

设V为当前车速，T为每辆车充电所需时间，当前有向网中每个点Vx，如果Vx为充电节点，该节点的numcars分量为等待充电电动汽车数量，distance分量为该节点由于有排队等待充电的电动汽车所造成的时间开销所折算的距离；如果Vx为非充电节点，则该节点的numcars分量设为-1，distance分量设为0；

具体算法描述为(算法2：充电节点等待时间-距离折算)：

If(Vx是充电节点)

Vx.distance=V*T*numcars；

else

{ Vx.distance=0；numcars=-1；}

通过算法2将当前有向网中每个充电点Vx由于等待充电排队汽车所造成的开销distance计算出来，将速度、等待充电车辆数量等非距离因素转换成距离来统一考虑.Floyd算法在解决有向网中各点之间最短距离问题上是最具优势的，剩下的问题可由改进的Floyd算法来解决.

具体算法描述为：(算法3：改进的Floyd算法)

Step1：初始化矩阵S和P；使得S中的元素s[i][j]表示顶点i到顶点j的距离权值，即s[i][j]=wij.矩阵P中的元素p[i][j]，表示顶点i到顶点j经过了p[i][j]记录的值所表示的顶点，初始时p[i][j]=j;

Step2：对于有向网中每个节点Vx：

If(Vx是充电节点)

Vx.distance=V*T*numcars；

else

{ Vx.distance=0；numcars=-1；}

Step3：For k:=1 to N

For i:=1 to N

For j:=1 to N

If s[i][j]>s[i][k]+s[k][j]

Then {s[i][j]:=s[i][k]+s[k][j];p[i][j]=p[i][k];}

Step4：s[i][j]=s[i][j]+Vj.distance

Step5：算法结束，矩阵S存储所有点对之间的最短路径长度与等待代价之和，矩阵P存储所有点对的最短路径信息.

2.2 随机构建有向联通网

改进Floyd算法在电动汽车充电中得以实现的基础是符合要求的有向网，而有向网的构造有固定生成法和随机产生法两种，固定生成法主要通过程序读入文件或输入固定参数的方法来生成图，生成的图用邻接矩阵来存储，这种方法产生的图具有一定的局限性，不利于对系统的综合测试及验证；随机生成网的方法就是随机产生图的顶点个数、图的边的个数以及边的权值.这种图的生成法可以随机快速地产生类型丰富的图或者网，效率比高，有利于对系统的综合测试及验证.

将两种方法的优点结合起来.主要通过随机生成的方法来生成所需要的图或网，同时综合考虑现实研究问题对应的图或者是网参数的合理范围，对随机生成图的参数范围进行合理限定，高效地产生出所需的有向网.在市区行驶中的电动汽车寻找合适充电点进行充电，可以考虑以当前点为源点，产生10～20个公路节点，在这10～20个公路节点里有3～8个充电点，在预先设定随机数范围来实现产生公路节点和充电节点，然后再设定各节点之间的距离.根据市区内的特点，可以将节点或充点电之间的距离设为5～15千米范围，也可以预先设定随机数范围的方式来确定，按照以上提出的思路来构建有向网络.在现实生活中,公路网一般是联通的，为了解决随机产生公路网可能存在不连通的状况，本文采用了一个限定办法：在随机产生了公路节点的数量m后，限定随机产生的路径数量不得小于m，且在构建前m条路径时先把m个节点串成一个闭环，在第m及以后条边的起点和终点采用随机选取的方式来确定，这样可以保证产生联通有向网.至于是否需要构建强联通网，考虑到城市道路中存在单行道的特点，我们在构建公路网络时不按照强联通网的特点来构建.随机有向网构建流程如图1所示.

图1 随机有向网构建流程

2.3 改进Floyd算法在随机有向网上的实现

根据上文分析，把需要充电的电动汽车所处位置环境抽象为有向连通网G=(V,E)，先随机生成连通网后，按照预设条件范围随机生成平均充电时间T和当前车速CV，设顶点集V中一共有M个节点，随机生成N个充电节点，N的范围是M/4<=N<=M/3，并对每个充电节点随机设置0～3辆等待充电汽车的数量.接下来，调用前文提出的算法2对于有向连通网中的每个节点Vx的distance分量进行计算，作为有向网中其余点到达该点距离的一部分.引入两个矩阵S、P，S中的元素s[i][j]表示顶点i到顶点j的距离权值.矩阵P中的元素p[i][j]，表示顶点i到顶点j经过了p[i][j]记录的值所表示的顶点.再按照前文提出的算法3求出该有向连通网各点之间的最小距离(含有distance因素的综合距离)，算法具体步骤如下：

Step1：初始化矩阵S和P；使得S中的元素s[i][j]表示顶点i到顶点j的距离权值，即s[i][j]=wij.矩阵P中的元素p[i][j]，表示顶点i到顶点j经过了p[i][j]记录的值所表示的顶点，初始时p[i][j]=j;随机生成N个充电节点，N的范围是M/4<=N<=M/3，并对每个充电节点随机设置0～3辆等待充电汽车的数量.

Step2：对于有向网中每个节点Vj，调用算法2计算设置Vj.distance

Step3：For k:=1 to N

For i:=1 to N

For j:=1 to N

If s[i][j]>s[i][k]+s[k][j]

Then {s[i][j]:=s[i][k]+s[k][j];p[i][j]=p[i][k];}

Step4：s[i][j]=s[i][j]+Vj.distance

Step5：对于任一非充电节点x，找到一个充电节点y使得s[x][y]=Min{s[i][j]|x==i&&j为充电节点}

2.4 系统测试与分析

本研究算法(包括随机生成有向网)采用C语言模拟实现，按照图1所示流程先生成一个有向联通网，在指定范围内随机预设当前车速及各充电桩等待充电汽车的数量，最后按照前文所提的改进Floyd算法找到合适的充点电并将路径返回.整个系统流程图如图2所示.

图2 系统流程图

本算法中的随机生成有向网部分，生成节点的部分算法复杂度为O(n)，生成有向边部分，考虑一个有向网为强联通网的情况下边的数量为n*(n-1)，而实际上公路存在单行道的情况，公路网不可能达到n*(n-1)条边的规模，所以随机生成网操作的时间复杂度为O(n2)；接下来调用前文提出的改进Floyd算法(算法3)结合每个充电点等待充电汽车数量等综合因素计算出每个点对之间的最短距离，最后，根据提出的非充电节点位置，计算出最佳充电点的位置并给出相应路径.Floyd算法的改进的核心思想是先计算出有向网中所有点对的最短距离，然后再结合每个充电点等待充电汽车数量,根据算法2更新每个点的distance分量，该分量将作为其余顶点达该点的最短距离的一部分，这样得出与充点电相关的各点对的最短距离就结合了排队等待的其他因素，使得选择方案更加科学、有效.

传统的Floyd算法的时间复杂度为O(n3)，对改进部分主要是计算每个点的distance分量和计算出每个点对之间的最短距离后结合目标点的distance分量确定指定起点的最佳充电位置及相应路径，这两改进部分的时间复杂度都是O(n).综合以上，改进的Floyd算法的时间复杂度还是O(n3)，相对来说时间复杂度较高.为电动汽车寻找最佳充电点和路径而设计的算法，考虑到电动汽车续航能力，设计的路网节点一般在20个以内，充电节点一般在路网节点的1/4～1/3之间，这样的路网规模运行本设计的Floyd算法是完全可行的.

系统分组进行测试，每组在其对应参数取值范围内测10次，如表1所示.

表1 系统运行表

通过表1，我们可以发现以下几点特征：

1.本文提出的算法将路网中的充电点存在的排队等待因素综合考虑到最短路径算法中，将Floyd算法改进并实现，经过系统测试，每组实验均能准确找到充电目标并输出正确的行驶路径，说明本文提供的算法正确并且可以解决以电动汽车寻找充电点为背景的问题.

2.一共6组实验，随着图的复杂度增加，改进Floyd算法运行时间也大幅提升，这与算法时间复杂度本身特性相一致.

3.Floyd算法时间复杂度比较高，但是经过分析是可以适用于本研究的背景课题，由理论分析与实验对比，对Floyd算法的改进没有提高算法的时间复杂度，且增加的时间开销(查找充电点运行时间)相对于整个算法运行时间可忽略不计.

综上分析，该算法运行达到了预期的结果.

3 结束语

本文通过研究相关经典的Floyd、Dijkstra等最短路径及其改进算法，提出一种实现随机生成有向联通网的方法.改进的Floyd算法经过测试，获得了预期的结果；该方法的应用提高了对图、网络中最短路径等相关算法研究的效率，具有一定的实用价值.

本文提出的随机生成连通网的方法虽然根据现实情况对相关参数进行了范围限定，力求生成与现实情况贴近的有向联通网，但考虑到随机生成时，有部分参数可能与实际情况有一定差异，在一定程度上会造成实验数据的偏差.在未来的研究中应考虑按照实际路网情况进行构图，并将参数信息存储到文件或是数据库中，不断充实、完善文件及数据库信息，使实验数据完全符合实际情况，当文件或数据库信息非常丰富时，可以通过随机抽取的方式来构建路网图，为相关算法提供更为准确的测试数据，进而获取更为准确的结论.