单源最短路径 贪心算法.doc

《单源最短路径 贪心算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三单源最短路径一、实验目的及要求 掌握贪心算法的基本思想 用c程序实现单源最短路径的算法 二、实验环境 Window下的vc 2010三、实验内容 1、有向图与单源点最短路径 2、按路径长度非降的次序依次求各节点到源点的最 短路径 3、Dijkstra算法四、算法描述及实验步骤   设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为Vj ，则Vj只有：源点到终点有直接的弧 ；从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。

2、即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。   若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点， 即：dist[i]=Min{ dist[k]

3、 Vk∈V-S } 利用公式就可以依次找出下一条最短路径。 在程序中c[][]表示带权邻接矩阵 ，  dist[]表示顶点到源点的最短路径 ，  p[]记录顶点到源点最短路径的前驱节点 ，  u源点，函数Way是递归的构造出最短路径的次序。  五、实验结果 程序执行的结果：六、源

4、代码#include#includeusingnamespacestd;#defineMAX999voidgetdata(int**c,intn){inti,j;intbegin,end,weight;for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j)c[i][j]=0;elsec[i][j]=MAX;}}do{cout<<"请输入起点终点权值(-1退出)：";cin>>begin;if(begin==-1)break;cin>>end>>weight;c[begin][end]=weight;}while(begi

5、n!=-1);}voidDijkstra(intn,intv,int*dist,int*prev,int**c){bools[MAX];inti,j;for(i=1;i<=n;i++){dist[i]=c[v][i];//从源点到各点的值s[i]=false;if(dist[i]==MAX)prev[i]=0;//最大值没有路径elseprev[i]=v;//前驱为源点}dist[v]=0;s[v]=true;for(i=1;i<=n;i++){inttemp=MAX;intu=v;for(j=1;j<=n;j++)if((!s[j])&&(dist[j]

6、st[j];}//不在集合里，值《temp，选最小值s[u]=true;for(j=1;j<=n;j++){if((!s[j])&&(c[u][j]1;i--){path[i]=pre

7、v[path[i+1]];//构造路径m--;}for(i=m;i<=end;i++){cout<";//输出路径}cout<<"bb"<<""<>n;int*dist=newint[n+1];int*prev=newint[n+1];int**c;c=newint*[n+1];for(i=0;i<=n;i++){c[i]=newint[n+1];}getdata(c,n);//获取数据intbegin=1,end;cout<<"请输入所求单源路径的起点终点：

8、";cin>>begin>>end;v=begin;Dijkstra(n,v,dist,prev,c);//计算路径PrintPath(prev,n,begin,end);//输出路径system("pause");}