XXXXXXXX研究生论文
2010～2011学年第 1 学期
科 目 图论及其应用
姓 名 XXXX
学 号 XXXXXXX
任课老师 XXXXX
2010年 12 月 10 日
Dijistra 算法解决城市道路最短路问题
摘要：通过Dijkstra算法编程计算出重庆市主城九区任意两区间的最短路径，在vc下实现一个顶点到其余各个顶点的所有最短路径的查找。 关键字：最短路径；Dijkstra算法
当前城市的规模越来越大，交通道路状况也越来越复杂，从城市的一个地方到另一个地方可能有很多种路径，如何从众多的路径中选择距离最短或者所需时间最短的路径便成了人们关注的热点。能够选择出一条最符合条件的路径会给我们的日常生活带来极大地方便。本文就通过找城市各地之间的最短距离路径为例，详细的介绍经典的最短路径算法Dijistra算法及其算法的实现。
一． Dijkstra算法概述
Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各定点最短路径算法，解决的是有向图中最短路径问题，当然对无向图也同样适用。Dijkstra算法用于计算一个源节点到所有其他节点的最
【3】
短代价路径，它是按路径长度递增的次序来产生最短路径的算法。
其基本原理是：每次新扩展一个距离最短的点，更新与其相邻接的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。
举例来说，如果图中的顶点表示城市，而边上的权重表示各个城市间的距离，Dijkstra算法可以用来找到两个城市之间的最短路径。
二．算法描述
1.基本思想
Dijkstra提出的是一种按路径长度递增的顺序产生最短路径的方法，即：把图中所有顶点分成两组，第一组S包括已经确定最短路径的顶点，初始时只含有源点；第二组V-S中包括尚未包括最短路径的顶点，初始时含有图中除源点以外的所有其他顶点。按路径长度递增
【4】
的顺序就是远点到各顶点的最短路径，逐个把第二组中的顶点加到第一组中去，直至S=V.
2.实现思路
整个网络用邻接矩阵cost[][]表示，其中规定：（1）两个顶点之间无直接路径，即
3.计算步骤
（1）dist初始存放源点到各顶点的权值。
（2）{dist（i）|Vi∈(V-S)}中最小值对应的顶点就是从源点Vi到其他顶点的最短路径中最短的一条所对应的顶点，即dist(j)=min{dist(i) ∈ (V—S)}。 (3)对于所有顶点Vk(Vk∈(V—S))，修改dist(k)的值：
dist(k)=min(dist[k]，dist[j]+cost[j，k])
再在修改后的dist[k]中进行第二步，求得第二个j，顶点Vj加入S集合中，第二条最短路径产生。重复(2)(3)步，直至求得从源点Vi到各顶点的最短路径为止。
三．程序实现
1.以重庆主城九区的交通网络为例，单从各个区的距离来看，构成的网络是一个无向图，由于我没有这些具体的数据，所以假设各区之间的交通道路组成如图一所示。地名与各顶点的对应关系如表一所示。
北碚 28 31 14 沙坪坝 10 江北 12 渝中 10 11 17 11 九龙坡 13 大渡口 14 巴南
顶点 地名 1 南岸 2 渝中 3 江北 4 渝北 5 北碚 6 7 8 9 九龙坡 图一 重庆市交通道路网
14 南岸 16 渝北 19 沙坪坝 大渡口 巴南 表一 地名与定点的对应关系
2.数据结构定义
该网络用邻接矩阵存储，其结构定义如下： #define MAXLEN 100 #define MAX 10000 typedef struct {
string vexs[MAXLEN];//图中的顶点的信息
double arcs[MAXLEN][MAXLEN];//存放图信息的邻接矩阵 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 = 0;i < mg.vexnum;i++) {
cout< cout<<\第\个顶点的信息:\ string xx; cin>>xx; mg.vexs[i] = xx; } for(i = 0;i < mg.vexnum;i++) for(j = 0;j < mg.vexnum;j++) mg.arcs[i][j] = MAX;//将矩阵中存放的距离初始化为最大值 for(k = 0;k < mg.arcnum;k++) { cout<<\第\条边的起始顶点编号和终止顶点编号：\cin>>i>>j; while(i < 1 || i > mg.vexnum || j < 1 || j > mg.vexnum) { cout<<\编号超出范围，请重新输入:\ cin>>i>>j; } cout<<\此边的权值：\cin>>h; mg.arcs[i-1][j-1] = h; mg.arcs[j-1][i-1] = h; } return mg; } 具体操作时，需要在主程序中输入顶点和边的信息（两个端点及权值），即交通网络的地名在主程序中的名称及两地之间是否有通路的信息，若有通路还需输入两地间的距 离。 4.主程序 在给出了数据结构类型及具体操作的算法之后，可以编辑出如下的主程序： int main() { MGRAPH mg; int cost[MAXLEN][MAXLEN]; int path[MAXLEN],s[MAXLEN];//path存放路径，s存放已确定最短路径的顶点 int dist[MAXLEN];//存放源点到个顶点的权值 int i,j,n,v0,min,u; mg = creat_mgraph();//建立有向图的邻接矩阵结构 cout< n = mg.vexnum; for(i = 0;i < n;i++)//cost矩阵初始化 { for(j = 0;j < n;j++) cost[i][j] = mg.arcs[i][j]; cost[i][i] = 0; } for(i = 0;i < n;i++) { dist[i] = cost[v0][i];//dist数组初始化 if(dist[i] < MAX&&dist[i] > 0) path[i] = v0;//path数组初始化 } for(i = 0;i < n;i++) s[i] = 0;//s数组初始化 s[v0] = 1; for(i = 0;i < n;i++) { min = MAX; u = v0; for(j = 0;j < n;j++) if(s[j] == 0&&dist[j] < min) { min = dist[j]; u = j; } s[u] = 1;//u顶点时求得最短路径的顶点编号 for(j = 0;j< n;j++) if(s[j] == 0&&dist[u] + cost[u][j] < dist[j]) { 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库图论及其应用在线全文阅读。
相关推荐：