最短路径算法浅析

甘肃科技

GansuScienceandTechnology

Vol.26　No.2Jan.　2010

最短路径算法浅析

贺　鹏,殷亚君

1

2

(1.甘肃紫光智能交通与控制技术有限公司,甘肃兰州730010;2.甘肃省高等级公路运营管理中心,甘肃兰州730000)

摘　要:高速公路网结构的数学模型是高速公路收费和清分的计算基础。介绍了用邻接矩阵来描述高速公路网的物理结构,讨论用Floyed算法计算路网中最短路径和路径长度,并给出了实现该算法的C语言程序。关键词:高速公路;联网收费;最短路径;Floyed算法中图分类号:U495

　　随着高速公路路网规模的不断扩大以及联网收

费的实施,必然会出现二义性路径问题。所谓二义性路径,是指从高速公路网某个入口至某个出口之间存在两条或者多条不同的路径。由于高速公路通行费的收取是以车辆在路网内的行驶里程为依据进行计算的,因此,二义性路径必然给通行费的计算带来困难。根据国内外建设经验,解决二义性路径问题的常用方法主要有两类。

(1)路径确认。通过在产生二义性路径的路段上设立标识站,或者采用车牌识别、GPS跟踪定位等技术手段来精确判断车辆行驶路径;

(2)不确认路径。在产生二义性路径的路段根据最短路径法、交通分布法、车型分类统计法或协商法等算法确定两点之间的唯一收费费率,即把起止点间的多条路径简化为费率惟一的一条虚拟路径来处理。

上述两类方法各有优缺点。设立标识站等技术手段虽然可以精确地判断车辆行驶路径,但系统的建设、维护、管理等成本费用可能会远大于精确判断车辆行驶路径而带来的通行费收益,同时也影响了高速公路的通行效率。因此,目前常见的做法是根据最短路径法来确定两点之间的唯一收费费率,通过协商法来解决通行费的拆分问题。介绍了高速公路路网结构的数学描述方法以及最短路径的算法及实现。

图1　高速公路网络结构示意里程)。实施联网收费的高速公路网络结构必然为一个连通图,即从任意顶点出发进行深度优先或广度优先搜索即可遍历图。

对于有n个顶点的网络,利用图论,可以用n×n的邻接矩阵G描述:

Wij　若顶点Vi,Vj相邻接

G[i,j]=∞　若顶点Vi,Vj不邻接

0　Vi=Vj

其中:Wij表示边上的权值。

则图1所示路网结构可表示为如下邻接矩阵:

0　45　∞　∞　∞　∞45　0　23　∞　∞　37G=

∞　23　0　∞　65　∞∞　∞　∞　0　43　∞∞　∞　65　43　0　80∞　37　∞　∞　80　0显然,矩阵G为对称矩阵。在用计算机存储或计算时可以用某个最大的权值或计算机可处理的最大数来代替∞。

1　高速公路路网结构的数学模型

高速公路网的物理结构可以用无向带权图(网络)来描述,如图1所示。

在图1中顶点V1、V2、…、V6表示高速公路匝道出入口,两点之间的边表示匝道出入口之间的连接关系,边上的权值表示两点之间的距离(实际行驶

2　最短路径算法及实现

目前已有众多成熟的最短路径算法,如,Dijk2stra算法,可以方便的计算某一顶点到其余各顶点

的最短路径。另一个典型算法是Floyed算法,可以计算图中每对顶点之间的最短路径。在使用最短路

第2期　　　　　　　　　　　　　贺　鹏等:最短路径算法浅析径法计算联网收费费率表时,需要计算出任意两个匝道出入口之间的最短路径,因此,更适合使用Floyed算法。

Floyed算法使用图的邻接矩阵A进行n次迭代

43

　　　　}}

3　实例分析

以图1所示路网结构为例,该路网用邻接矩阵G表示:

0　45　∞　∞　∞　∞45　0　23　∞　∞　37G=

来计算每对顶点间的最短路径,迭代过程中得到一

01nn

个矩阵序列A,A,…,A,矩阵元素A[i,j]的值即为从顶点i到顶点j的最短路径。首先在路径(i,j)中插入顶点0,考虑路径(i,0,j),若该路径存在,比较路径(i,j)和路径(i,0,j)的长度,取长度较短者作为从顶点i到顶点j且中间顶点编号不大于0的最

1

短路径存入A[i,j]中,记为(i,…,j),然后考虑路径(i,…,1,…,j),求得从i到j且中间顶点编号不大于1的最短路径存入A[i,j]。依此类推,逐个插

k+1

入图中的每个顶点,在k+1次迭代时,矩阵A[i,j]的值为:

A

k+1

∞　23　0　∞　65　∞∞　∞　∞　0　43　∞∞　∞　65　43　0　80∞　37　∞　∞　80　02

[i,j]=mink+1

A[i,j]

A[i,k]+A[k,j]

k

k

k

其中A[i,j]表示经过k+1次迭代后得到的值,等于从i到j且中间顶点编号不大于k的最短路

3

径长度。该算法复杂度为0(n)。

下面是Floyed算法求每对顶点之间最短路径的C语言程序,程序中矩阵A用来进行n次迭代,矩阵P用来记录路径,P[i,j]为迭代过程中当前已经求得的从顶点i到顶点j的最短路径上最后被插入的那个顶点。

voidFloyed(GraphG,intA[n][n],intP[n][n]){

　inti,j,k;

　for(i=0;i　　　A[i][j]=G[i][j];　　　if(A[i][j]>0)　　　　P[i][j]=i;　　　else

　　　　P[i][j]=0;　　}

　for(k=0;k　　　　if(A[i][k]+A[k][j]　　　　　P[i][j]=k;

　　　　　A[i][j]=A[i][k]+A[k][j];

用上文描述的算法求得最短路径矩阵A和路径矩阵P:

0　45　　68　176　133　8245　0　　23　131　88　3768　23　　0　108　65　60A=

176　131　108　0　43　123133　88　　65　43　0　8082　37　　60　123　80　00　1　2　5　3　22　0　2　5　3　2P=

2　3　0　5　3　22　3　5　0　4　52　3　5　5　0　52　6　2　5　6　0由矩阵A和P可查出任意两个顶点之间的最短路径和长度,例如:V1至V4最短路径长度为A[1,4]=176;根据矩阵P的定义,P[i,j]为迭代过程中当前已经求得的从顶点i到顶点j的最短路径上最后被插入的那个顶点,由P[1,4]依次向前回溯:P[1,4]=5,P[1,5]=3,P[1,3]=2,P[1,2]=1,即由V1至V4的最短路径经过的顶点依次为V1、

V2、V3、V5、V4。

4　结语

用邻接矩阵表示高速公路网的结构,不仅可以详细描述出路网的物理结构,而且与二维表的结构相近,易于程序实现和存储,具有较强的实用性。这里仅讨论了用图中的顶点表示匝道出入口的情况,实际应用中,顶点也可以表示高速公路分叉口或分隔不同业主所属路段的虚拟节点,只要加入对顶点属性的描述即可。

(下转第33页)

第2期　　　　　　　　　杨力铭等:涉密内网中的移动存储介质管理问题及对策2.2.5　文件安全删除

33

移动存储介质上的文件和文件夹采用常规方法删除以后,还是可以使用专门的技术和工具进行恢

[5]

复的。对于涉密等级较高的资料应采用更加彻底的办法加以“粉碎”,确保资料在删除后不能被恢复。可采用密码置乱技术,对删除文件后的移动存储设备进行8次随机数填充,即没有对移动存储设备进行硬件破坏又保证任何工具都不能恢复移动存储设备上的数据。2.2.6　记录使用日志

对移动存储介质上所有的文件操作,包括文件的创建、复制、删除和重命名等操作,进行详细的监控记录,记录的要素包括时间、用户名、计算机名、文件名和其他必要的信息,以作为日后审计使用。如此一来,即便发生通过移动存储介质造成的泄密问题,也有据可查,可以为追究责任和防堵漏洞提供有力的证据保障。

2.3　三权分立的管理机制

此,可将可移动存储介质划分保密等级,用以存放相

应密级的数据,只有具备相关权限的人员才能对涉密信息进行访问。密级对应不是说只有同等密级的计算机和移动存储介质之间才能建立互信的使用关系,按照密级对应使用移动存储介质的一般原则是:数据从低密向高密流动不受限制。如,高密级计算机能读取低密级移动存储介质上的数据,但不能对其进行写入操作。按照密级对应的使用原则,即灵活又有效的构筑了一道防止涉密信息泄露的安全堤坝。

[6]

3　结束语

移动存储介质安全管理是内网信息安全管理的重要组成部分。移动存储介质的使用范围越来越广,必须因势利导,坚持预防为主的方针,通过认证和加密技术,提高了移动存储介质使用的安全性。但是,一个完整的内网安全系统应是技术手段和管理制度相结合的体系,还需要对涉密移动存储介质进行全过程监管,严把采购关、检查关、使用关、维护关及销毁关等各个环节,形成“制度保障、组织管理、技术防范”的整体合力,从而构建一个安全的可信赖的内部网络工作环境。

参考文献:

[1]　王琢,刘建华,范九伦.Autorun类病毒在移动存储中的

对于某些管理要求严格的大型企事业单位的涉

密内网,对移动存储介质管理除了使用技术加以管控以外,还可进一步采用三权分立的管理机制。三权指的是:管理员权限、审计员权限、操作员权限。管理员负责本级用户标识设备的创建和管理,负责下级管理员和审计员的生成和管理等;审计员负责提取所有角色的操作日志,必要时加以分析和取证。在移动存储设备的使用过程中,审计员可随时提取包括注册信息、使用人、使用计算机、使用时间、使用信息和动作等审计记录,可以对移动存储设备的整个使用过程进行监督和审计;操作员负责移动存储介质的注册、授权、注销等等具体操作。2.4　密级对应的使用原则

信息是分密级的。在一个合格的安全体系中,不同密级的信息必须保存在不同的位置或不同的存储介质上,这样便于最大限度保障信息的安全。为(上接第43页)

传播方式分析[J].计算机安全,2008(11):108Ο109.

[2]　池同柱,陈平.浅谈移动存储介质的信息安全[J].技

术研究与应用,2008(10):62.

[3]　周俐军,王冬梅,宋皓.政务内网中的移动存储介质管

理问题及对策[J].电子政务,2008(10):97.

[4]　池同柱,陈平.浅谈移动存储介质的信息安全[J].技

术研究与应用,2008(10):63.

[5]　闫安.论数据误删除后的恢复及数据的安全删除[J].

网络与信息,2008(12):26Ο28.

[6]　张秋江,王澎.涉密网络的一体化安全防护技术[J].

信息安全与通信保密,2007(3):143.参考文献:

[1]　陈庆喜.浅析高速公路路网模型的建立与清分算法的

讨论的Floyed算法基于图论的矩阵理论,是非

常有特点的一个传统算法。该算法可以方便的计算每对顶点之间的最短路径和长度,如果加入车型收费标准、各路段所属业主的数学描述,便可以很方便地计算出收费费率表和拆分表。当路网结构发生变化时,只需修改模型的输入参数,即可自动计算费率,从而实现费率表和拆分表的自动维护,极大地提高工作效率,确保费率的准确性。

实现[J].筑路机械与施工机械化,2004(11):53Ο57.

[2]　童剑军.高速公路联网收费路径识别技术应用问题的

提出———“二义性路径”[J].交通信息产业,2006(3):

16Ο17.

[3]　陈剑威,罗石贵.路径识别技术选择的基本考虑[J].

交通信息产业,2006(3):25Ο26.