图论及其应用

1、 XXXXXXXX研究生论文20102011学年第 1 学期科 目 图论及其应用 姓 名 XXXX 学 号 XXXXXXX 任课老师 XXXXX 2010年 12 月 10 日Dijistra 算法解决城市道路最短路问题摘要：通过Dijkstra算法编程计算出重庆市主城九区任意两区间的最短路径，在vc下实现一个顶点到其余各个顶点的所有最短路径的查找。关键字：最短路径；Dijkstra算法当前城市的规模越来越大，交通道路状况也越来越复杂，从城市的一个地方到另一个地方可能有很多种路径，如何从众多的路径中选择距离最短或者所需时间最短的路径便成了人们关注的热点。能够选择出一条最符合条件的路径会给我们的

2、日常生活带来极大地方便。本文就通过找城市各地之间的最短距离路径为例，详细的介绍经典的最短路径算法Dijistra算法及其算法的实现。一 Dijkstra算法概述Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各定点最短路径算法，解决的是有向图中最短路径问题，当然对无向图也同样适用。Dijkstra算法用于计算一个源节点到所有其他节点的最短代价路径，它是按路径长度递增的次序来产生最短路径的算法。【3】其基本原理是：每次新扩展一个距离最短的点，更新与其相邻接的点的距离。当所有边权都为正时，由于不会存在一个距离更短的

3、没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。举例来说，如果图中的顶点表示城市，而边上的权重表示各个城市间的距离，Dijkstra算法可以用来找到两个城市之间的最短路径。二算法描述1.基本思想Dijkstra提出的是一种按路径长度递增的顺序产生最短路径的方法，即：把图中所有顶点分成两组，第一组S包括已经确定最短路径的顶点，初始时只含有源点；第二组V-S中包括尚未包括最短路径的顶点，初始时含有图中除源点以外的所有其他顶点。按

4、路径长度递增的顺序就是远点到各顶点的最短路径，逐个把第二组中的顶点加到第一组中去，直至S=V.【4】2.实现思路整个网络用邻接矩阵cost表示，其中规定：（1）两个顶点之间无直接路径，即<Vi,Vj>弧不存在，矩阵中对应权值为无穷大；（2）两个顶点之间有直接路径<Vi,Vj>的，矩阵中的权值就是<Vi,Vj>弧对应的两点间的权值，当然根据实际的问题这里既可以是两地之间的距离也可以是两地间需要的费用等；（3）<Vi,Vi>对应的值为0.S集合初始存放在最短路径的源点，计算过程中将已经确定了最短路径的点加入到S中去，本人的思路是每个点对应数组里对应的

5、值，若确定了某顶点时最短路径的点则将其对应的值变为1，知道所有的点对应的值变为1。dist数组最终存放源点到各顶点最短路径的结果。Path数组最终存放源点到各顶点的最短路径经过的顶点。3.计算步骤（1）dist初始存放源点到各顶点的权值。（2）dist（i）|Vi(V-S)中最小值对应的顶点就是从源点Vi到其他顶点的最短路径中最短的一条所对应的顶点，即dist(j)=mindist(i) (VS)。 (3)对于所有顶点Vk(Vk(VS)，修改dist(k)的值：dist(k)=min(distk，distj+costj，k)再在修改后的distk中进行第二步，求得第二个j，顶点Vj加入S集合中

6、，第二条最短路径产生。重复(2)(3)步，直至求得从源点Vi到各顶点的最短路径为止。三程序实现1.以重庆主城九区的交通网络为例，单从各个区的距离来看，构成的网络是一个无向图，由于我没有这些具体的数据，所以假设各区之间的交通道路组成如图一所示。地名与各顶点的对应关系如表一所示。28311410111911141316大渡口九龙坡沙坪坝南岸北碚渝北江北渝中12101417巴南图一 重庆市交通道路网顶点123456789地名南岸渝中江北渝北北碚沙坪坝大渡口巴南九龙坡表一 地名与定点的对应关系2.数据结构定义该网络用邻接矩阵存储，其结构定义如下：#define MAXLEN 100#define MA

7、X 10000typedef struct string vexsMAXLEN;/图中的顶点的信息 double arcsMAXLENMAXLEN;/存放图信息的邻接矩阵int vexnum,arcnum;/顶点的数目和边数MGRAPH;3.构造算法依据上述结构我们可以构造表示上述交通网络的有无向向网。其算法如下：MGRAPH creat_mgraph() int i,j,k; double h;MGRAPH mg;cout<<"请输入顶点数和边数:"cin>>i>>j;mg.vexnum = i;mg.arcnum = j;for(i

8、= 0;i < mg.vexnum;i+) cout<<endl;cout<<"第"<<i+1<<"个顶点的信息:" string xx;cin>>xx;mg.vexsi = xx; for(i = 0;i < mg.vexnum;i+)for(j = 0;j < mg.vexnum;j+) mg.arcsij = MAX;/将矩阵中存放的距离初始化为最大值for(k = 0;k < mg.arcnum;k+)cout<<"第"<&l

9、t;k+1<<"条边的起始顶点编号和终止顶点编号："cin>>i>>j;while(i < 1 | i > mg.vexnum | j < 1 | j > mg.vexnum)cout<<"编号超出范围，请重新输入:"<<endl; cin>>i>>j;cout<<"此边的权值："cin>>h;mg.arcsi-1j-1 = h;mg.arcsj-1i-1 = h; return mg; 具体操作时，需要

10、在主程序中输入顶点和边的信息（两个端点及权值），即交通网络的地名在主程序中的名称及两地之间是否有通路的信息，若有通路还需输入两地间的距离。4.主程序在给出了数据结构类型及具体操作的算法之后，可以编辑出如下的主程序：int main() MGRAPH mg; int costMAXLENMAXLEN; int pathMAXLEN,sMAXLEN;/path存放路径，s存放已确定最短路径的顶点 int distMAXLEN;/存放源点到个顶点的权值 int i,j,n,v0,min,u; mg = creat_mgraph();/建立有向图的邻接矩阵结构 cout<<endl<

11、<"请输入起始点的编号："/ 有向图中顶点的编号从1编起 cin>>v0; v0-; n = mg.vexnum; for(i = 0;i < n;i+)/cost矩阵初始化 for(j = 0;j < n;j+) costij = mg.arcsij; costii = 0; for(i = 0;i < n;i+) disti = costv0i;/dist数组初始化 if(disti < MAX&&disti > 0) pathi = v0;/path数组初始化 for(i = 0;i < n;i+)

12、 si = 0;/s数组初始化 sv0 = 1; for(i = 0;i < n;i+) min = MAX; u = v0; for(j = 0;j < n;j+) if(sj = 0&&distj < min) min = distj; u = j; su = 1;/u顶点时求得最短路径的顶点编号 for(j = 0;j< n;j+) if(sj = 0&&distu + costuj < distj) distj = distu + costuj; pathj = u;/path记录了通过路径的顶点 for(i = 0;i &

13、lt; n;i+)/打印结果 if(si = 1) u = i; while(u != v0) cout<<mg.vexsu<<"<-" u = pathu; cout<<mg.vexsu<<" dist = "<<disti<<endl;else cout<<i+1<<"->"<<v0+1<<"无路径"<<endl;return 0;四实验结果该程序在vc6.0下调试通过

14、，按程序提示的要求输入相应的数据。如提示请输入顶点数和边数时，按前面给的重庆交通网络图需输入9 13；接着提示输入第一个顶点的信息，按要求可输入Nanan，随后依次输入剩余八个点的信息；紧接着提示输入第一条边的起始顶点编号和终止顶点编号，输入1 2，后又提示此边权值，输入10，其余各边同样按这个步骤输入。这些必要信息输入完后，要求输入起始点的编号，由于篇幅有限，这里以1为例，显示其结果为：如果在该类网中动态的增加顶点和边，只需在运行程序时，输入增加以后的总顶点数、边数、顶点信息和边的起始顶点编号和终止顶点编号即可。五总结Dijkstra算法是求最短路的一个经典算法，其时间复杂度为O（n2）。最短路径对交通、道路问题的研究有重要的意义。该算法能够解决实际生活中的道路选择问题