《运筹学C语言实现Dijkstra算法求解图的最短路径.doc》由会员分享，可在线阅读，更多相关《运筹学C语言实现Dijkstra算法求解图的最短路径.doc（12页珍藏版）》请在三一文库上搜索。
1、西安科技大学运筹学课程设计报告姓名：袁薪洋Dijkstra算法思想为：设G=（V,E）是-个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合 （用S表示，初始时S中只有个源点，以后每求得r 、 r /art . . - t a 、. 一t . r r 、 、 _ ， tt条最短路径，就将运用Dijkstra算法求解图的最短路径加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第 二组为其余未确定最短路径的顶点集合（用 U表示），按最短路径长 度的递增次序依次把第二组的顶点加入 S中。在加入的过程中，总 保持从源点v到S中各顶点的最短路径长度不大于从源点 v到U中
2、任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是 从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。二、算法流程或步骤Dijkstr算法具体步骤：（1 ）初始时，S只包含源点，即S =, v的距离为0。U包含除v 外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。（2）从U中选取一个距离v最小的顶点k，把k,加入S中（该 选定的距离就是v到k的最短路径长度）。（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源 点v到顶点u （u U）的距离（经过顶点k）比原来距离（不经过顶
3、点k）短，则修改顶点u的距离值，修改后的距离值的顶点 k的距离加上边上的权。(4) 重复步骤(2)和(3)直到所有顶点都包含在 S中三、算法源程序#i nclude <iostream.h>int m;int n;float a100100;float dist100;int prev100;float MAX_V ALUE=10000;void dijkstra()if(m<0|m> n)/当无顶点的情况return;bool *s=new bool n+1;for(i nt i=0;i <n ;i+)disti=a0i;/与源点相连的权值si=false;if
4、(disti=MAX_V ALUE) /与源点无连接的顶点previ=O;/设置对应权值为elseprevi=m;/与源点相连接的顶点设置为mdistm=O;sm=true;for(i nt i1=0;i1< n;i1+)float temp二MAX_V ALUE;int u=m;for(i nt j=O;j <n ;j+)if(!sj)&&(distjvtemp) 与源点相连的顶点u=j;temp=distj;/设置temp成为与源点相连的顶点权值su=true;for(i nt j1=0;j1< n;j1+)if(!sj1)&&( auj1
5、<MAX_V ALUE)float newdist二distu+auj1;/算出与源点不直接相连的权值和if(n ewdist<dist|j1) distj1二n ewdist;prevj1=u;void path()for(i nt i=0;i <n ;i+)if(i!=m&&disti<MAX_V ALUE)（终点位置）coutvv"由源到顶点"<<i<<"的最短路径为:"<<i;int temp=i;dotemp=prevtemp;coutvv" <- &q
6、uot;vvtemp;while(temp!=m);coutvv"（源位置）。最短路径长度为："v<distiv<e ndl;void mai n()coutvv"请输入顶点的个数："cin>>n;coutvv"请分别对两顶点之间赋权值(若无此连接，赋0值,请注意 两顶点之间的方向):"<<endl;for(i nt i=0;i <n ;i+)for(i nt j=0;j <n ;j+)if(i=j)con ti nue;coutvv"顶点"vvivv"到顶
7、点"vvjvv"的权值为："ci n>>aij;if(aij=0) aij=MAX_V ALUE;coutvv"请输入此带权有向图的源顶点的编号："cin>>m;dijkstra();path();四、算例和结果例：设0为源点，求0到其他各顶点（1、2、3）的最短路径。1k眷Si?醫叱Dr叱斤加 叱叱叱斤羽嘶蟲 e m-m-ED-Xl210310320321 >EN*-z c / 5*#；W3還宅声W&S3I洌松Z色3"回初 X XX 卜530526323063 崙6 H富毋毋毋5稲!旁園回方回方
8、诣回那i词珈51 o扇萄苏皺陀Dr加Dr鉛GOr?陀h加h加叶4涯 S333222111000 出°善芝晋己妙世啊世啊凹购凹购地凹购寿J<歸歸鲫歸歸歸2o出巴出囹面商崗崗丽谕喻崗商商崗且J” o n>xa>» rp»vj 二 vif vif j 二 7 j二 7 vif Ji vi vii kj 二 4 _xx-xxXxJ>7-< -n< -T"<< -i < -T"< I<< j"< -i < -T"< -T"<ct H>iH只H只缶“ 才凶沁迢-U DrOrl SHcncMo MMMM v y 7 0