Dijkstra算法在城市道路网络中的应用

《Dijkstra算法在城市道路网络中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络通讯与安全本栏目责任编辑：冯蕾Dijkstra算法在城市道路网络中的应用渠寒花，王丽娜，周杰（南京信息工程大学电子于信息工程学院，江苏南京210044）摘要：本文介绍了一个利用自然语言处理技术进行城市交通查询的系统。在研究城市道路网络特征基础上，建立城市道路网络模型及其数据库，应用Dijkstra算法对城市道进行最短路径查询，该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索，并得到良好的查询结果。关键词：交通网络；数据库；Dijkstra算法；最短路径中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)22-40984-03

2、DijkstraAlgorithminUrbanRoadNetworkApplicationQUHan-hua，WANGLi-na，ZHOUJie(CollegeofElectronic&InformationEngineering,NanjingUniversityofInformationScience&Technology,Nanjing210044,China)Abstract:Thispaperpresentsourrecentworkstowardsthedevelopmentofpublictransportationnaturallanguagequerys

3、ystem.Itestablishedtheroadnetmodelanddatabaseofurbantrafficbasedonthestudyoftheurbantrafficroadcharacter.TheshortestpathwasqueriedbytheimprovingDijkstraarithmetic,andobtainabetteroutcome.Keywords:transportationnetwork;datebase;Dijkstraarithmetic;shortes'path1引言的有序元素对。(u,v)表示从顶点u到v有路径相连。我城市

4、化水平的提高,城市区域范围逐步扩大,人们们以E所有边的集合，而边的权重则由权重函数w：E→在城市之间的活动频度不断增加，城市交通网络在现代[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负生活中起着越来越重要的作用。一般来说,人们都会选花费值(cost)。边的花费可以想像成两个顶点之间的距择合适自己的最佳路径。两城市间的“最佳路径”可能需离，任两点间路径的花费值，就是该路径上所有边的花要考虑的并非仅仅是“空间距离”的最短,还有“时间最费值总和。已知V中有顶点s及t，Dijkstra算法可以找短”和“费用最小”。到s到t的最低花费路径(i.e.最短路径)。但是，交通

5、需求不断增长、交通系统日益复杂，单独讨论单源点的最短路径问题，使用Dijkstra算法，给从车辆方面或道路方面考虑，均很难有效地解决交通问定带权有向图G和源点V，求从V到G中其余各源点题。于是，近年来把道路、车辆等，凡与交通有关的所有的最短路径。引进一个辅助变量D，它的每个分量D[i]表一切都归为一体，通过采用信息通信技术、电子技术以示当前所找到的从始点V到每个终点Vi的最短路径的及其他的科学技术把它们联系起来，致力于使之智能化长度，它的状态为：若从V到Vi有弧，则D[i]为弧上的的交通系统的研究开发应运而生，交通信息系统的复杂权值，否则置D[i]为∞，显然，长度为D[j]

6、=Min{D[i]

7、Vi∈性决定了建设信息化交通查询系统的必要性。DijkstraV}的路径就是从V出发的长度最短的一条最短路径，此算法是最适合网络拓扑中两结点间最短路径搜索的算路径为(Vi,Vj)。法之一。本文讨论公路交通网络中两结点间的最短路径2.2Dijkstra算法步骤搜索问题，从核心算法方面对Dijkstra算法进行改进。采用有向图G(V，E)来表示图1中的交通图，讨论2Dijkstra算法Dijkstra算法的计算步骤。2.1Dijkstra算法概述其中：Dijkstra算法是由荷兰计算机科学家艾兹格·迪科Vi——顶点号；斯彻发现的，算法解决的是有向图中最短路径

8、问题。→——单向通道；Dijkstra算法的输入包含了一个有权重的有向图d(vi,vj)——从Vi顶点到Vj顶点的费用；G，以及G中的一个来源顶点S。我们以V表示G中所1，6，3，2⋯⋯——路径之间的权值。有顶点的集合。每一个图中的边，都是两个顶点所形成步骤1：收稿日期：2007-10-25作者简介：渠寒花（1984-），女，江苏南京人，硕士研究生；周杰（1964-），男，江苏南京人，教授，博士。984电脑知识与技术本栏目责任编辑：冯蕾网络通讯与安全线的目的。3城市交通模型对于一个城市交通网要考虑道路等级，不同等级