最优交通路径
开篇：润墨网以专业的文秘视角，为您筛选了一篇最优交通路径范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：随着全球经济的腾飞，对交通运输的需求越来越迫切。怎样有效地提高现有交通运输的效率，这就是所要研究的主要问题，最优交通路径算法。它是利用Dijkstra解决最优路径问题，它通过分步方法求出最短路径。最优路径中的“优”包括很多层面，它可以是一般地理意义上的距离最短，还可以是时间最短、费用最少、线路利用率最高等多方面。但是无论哪种判断标准，其核心实现方法都是最短路径算法。对于交通公路来说，距离因素是最重要的，所以在论文的中，主要讨论距离最短的路径。
关键词：最短路径算法；线路利用率；子程序
中图分类号：TP311文献标识码：A文章编号：1009-3044(2010)20-5574-03
The Most Optimal Path Traffic
WEI Qing
(Computer Science and Electronic Information Engineering Department, Heze University, Heze 274015, China)
Abstract: With the global economy to take off, to the transport needs of more and more pressing. How to effectively improve the efficiency of existing transport, which is the main issue to be studied, optimal traffic path algorithm. It is the optimal path using Dijkstra to solve the problem, which by-step method to find the shortest path. Optimal path in the "You" includes a lot of meaning, it not only refers to the general geographic sense, the shortest distance, but also is the shortest, least-cost, line utilization rate of the highest standards. But no matter what kind of extended criterion, the core realization is the shortest path algorithm. For road transport, the distance factor is most important, so in the paper, the main discussion of the shortest path distance.
Key words: shortest path algorithm; line use factor; subroutine
随着地理信息产业的建立在全世界的普及，地理信息系统已深入到各行各业甚至各家各户，成为人们生产、生活学习和工作中不可缺少的工具和助手。地理信息系统中网络分析功能的主要目的是对交通网络。最短路径问题是交通网络分析中的最基本最关键的问题，它对于交通运输线路的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。
1 最优交通路径功能介绍
程序中设置了国内部分城市间的距离，然后对用户选择的两个城市，计算出两个城市之间的最短距离，以及连接它们的相应路线。
2 最优交通路径程序使用算法描述
假设我们用邻接矩阵表示所研究的图,规定对角线元素取零值,各有向边的元素取该边的权值,若两顶点间无相应方向的边,则该元素取无穷大。此矩阵用一个（n*n）二维数组表示，无穷大元素用一个很大的有限值代替，如果得到的某路径“长度”等于此给定的很大值，说明实际上不存在此路径。首先引入两个辅助向量，一个是向量dist，它的每个分量dist[i]表示当前找到的从始点V 到每个终点Vi 的最短路径长度。另一个向量是S，S 为已找到的从V 出发的最短路径的终点的集合，其初始值为空集。
3 最优交通路径程序设计的实现过程
3.1 最优交通路径程序设计的步骤
定义数据结构。
第一、用CreateUDN()函数生成一个交通图。
第二、用narrate()函数进行格式输入。
第三、用shortestpath()生成最短路径算法。
第四、用output函数把计算的结果格式输出。
3.2 城市交通图及图的存储类型定义
因为两个城市间距离是互相的，所以可把图3部分城市交通图看作一个无向图，把图中的城市看作无向图中的顶点，任意两个顶点之间都存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的联系，即没有顺序存储结构，可借助结构数组的数据类型表示元素之间的关系。
结构体的定义：
1) 边的类型定义：
typedef struct ArcCell{
int adj;/*相邻接的城市序号*/
}ArcCell; /*定义边的类型*/
2) 顶点的类型定义：
typedef struct VertexType{
int number;/*城市序号*/
char city; /*城市名称*/
}VertexType; /*定义顶点的类型*/
3) 图的类型定义：
typedef struct{
VertexType vex[25];/*图中的顶点，即为城市*/
ArcCell arcs[25][25]; /*图中的边，即为城市间的距离*/
int vexnum,arcnum; /*顶点数，边数*/
}MGraph; /*定义图的类型*/
3.3 图的构造过程
图的存储结构定义完成后，开始构造图。
1) 为每个城市编写一个序号，从0开始至24。以乌鲁木齐为数组的起点，依次为西宁，兰州，呼和浩特，北京，天津，沈阳，长春，哈尔滨，大连，西安，郑州，徐州，成都，武汉，上海，昆明，贵州，株州，南昌，福州，柳州，南宁，广州，深圳。Creatudn()函数根据用户输入的顶点数和边数生成一个相应的交通图，其顶点对应于城市，边对应于城市间的直接通路，能生成一个拥有25个城市，30条公路的交通图。具体程序段如下：
G.vexnum=v;
G.arcnum=a;
for(i=0;i
/*下边是城市名*/
G.vex[0].city="乌鲁木齐";
G.vex[1].city="西宁";
G.vex[2].city="兰州";
G.vex[3].city="呼和浩特";
G.vex[4].city="北京";
G.vex[5].city="天津";
G.vex[6].city="沈阳";
G.vex[7].city="长春";
G.vex[8].city="哈尔滨";
G.vex[9].city="大连";
G.vex[10].city="西安";
G.vex[11].city="郑州";
G.vex[12].city="徐州";
G.vex[13].city="成都";
G.vex[14].city="武汉";
G.vex[15].city="上海";
G.vex[16].city="昆明";
G.vex[17].city="贵州";
G.vex[18].city="株洲";
G.vex[19].city="南昌";
G.vex[20].city="福州";
G.vex[21].city="柳州";
G.vex[22].city="南宁";
G.vex[23].city="广州";
G.vex[24].city="深圳";
2) 可直接到达的城市，城市间距离是相互的，所以要对图中对称的边同时付值，程序部分节选如下（G.arcs[i][j].adj表示的是序号为i的城市与序号为j的城市之间的距离）：
G.arcs[0][2].adj=G.arcs[2][0].adj=1892;
G.arcs[1][2].adj=G.arcs[2][1].adj=216;
G.arcs[2][3].adj=G.arcs[3][2].adj=1145;
G.arcs[2][10].adj=G.arcs[10][2].adj=676;
3.4 最优交通路径函数的描述
如何求的最短路径？可以按路径长度增长的次序产生最短路径：
第一、先定义v到w的权值和最短路径集合，用带权的邻接钜阵arcs表示带权无向图，arcs[v][w].adj表示到上的权值，若不存在，则置arcs[v][w].adj为∞（既为程序中的20000），min为找到从v出发的最短路径的终点的集合，它的初始状态为空集，那么从v出发到图上其余各顶点w可能达到的最短路径长度处值为arcs[v][w]。
第二、选择min使min=min{arcs[v][w]}。
第三、修改以v出发到v―min上任一顶点w可达的最短路径长度，如果Min+G.arcs[v][w].adj
第四、重复操作第一、第二共n-1次。由此求得从v到图上其余各顶点的最短交通路径是依据长度递增的序列。
第五、时间复杂度：第一个for循环时间是0(n),第二个for循环共进行n-1次，
每次执行时间是0(n),所以总时间是0(n2)。
综合上面的过程，可以发现：
1) 将起点插入树中。
2) 找出图中所有顶点的邻接边，总和最小的边。
3) 重复第二步骤，直到所有的顶点都在树中为止。
最短路径程序如下：
void ShortestPath(intnum) /*最短路径函数*/
{ int v,w,i,t;
int final[25];
int min;
for(v=0;v
{ final[v]=0;D[v]=G.arcs[num][v].adj;
for(w=0;w
if(D[v]
D[num]=0;final[num]=1;
for(i=0;i
{min=20000;
for(w=0;w
if(!final[w])
if(D[w]
final[v]=1;
for(w=0;w
if(!final[w]&&((min+G.arcs[v][w].adj)
{ D[w]=min+G.arcs[v][w].adj;
for(t=0;t
P[w][w]=1; }}}
4 总结
本文从空间分析的角度出发，较详细的研究了网络分析中最短路径问题，以及在最短路径基础上的路线查询。其特点如下：
1) 采用图的结点――弧段联合结构表示路线的相互关系，建立了网络要素之间的拓扑结构，从而较方便的查询交通信息及最短路径。
2) 在Dijkstra算法的基础上，用邻接点算法来优化最短路径问题，在一定程度上节省了存贮空间和提高了运算速度。
参考文献：
[1] 边馥苓.地理信息系统原理和方法[M].北京:测绘出版社,1996.
[2] 唐邦民,谢晗昕.数据结构与算法分析[M].北京:电子工业出版社,2005.
[3] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.
[4] 刘家壮,王建方.网络最优化[M].武汉:华中工学院出版社.1987.
[5] 曹丽明.图论及其在计算机科学中的应用[M].徐州:中国矿业大学出版社,1995.
[6] 韩鹏.地理信息系统开发[M].武汉:武汉大学出版社,2004.