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

实验三 单源最短路径 一、实验目的及要求? 掌握贪心算法的基本思想? 用c程序实现单源最短路径的算法? 二、实验环境? Window下的vc?2010 三、实验内容? 1、有向图与单源点最短路径? 2、按路径长度非降的次序依次求各节点到源点的最?短路径?3、Dijkstra算法 四、算法描述及实验步骤? ??设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs}?。当求得第一条最短路径(Vs?，Vi)后，S为{Vs，Vi}?。根据以下结论可求下一条最短路径。? 设下一条最短路径终点为Vj?，则Vj只有：源点到终点有直接的弧? Vs，Vj；从Vs?出发到Vj?的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj?。? ??若定义一个数组dist[n]，其每个dist[i]分量保存从Vs?出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，? 即：dist[i]=Min{?dist[k]|?Vk∈V-S?}? 利用公式就可以依次找出下一条最短路径。? 在程序中c[][]表示带权邻接矩阵?，??dist[]表示顶点到源点的最短路径?，??p[]记录顶点到源点最短路径的前驱节点?，??u源点，函数Way是递归的构造出最短路径的次序。? ? 五、实验结果? 程序执行的结果： 六、源代码 #include iostream #includestdlib.h using namespace std; #define MAX 999 void getdata(int **c,int n) { int i,j; int begin,end,weight; for (i=1;i=n;i++) { for (j=1;j=n;j++) { if(i==j) c[i][j]=0; else c[i][j]=MAX; } } do { cout请输入 起点 终点 权值(-1退出)：; cinbegin; if(begin==-1) break; cinendweight; c[begin][end]=weight; } while(begin!=-1); } void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i=n;i++) { int temp=MAX; int u=v; for(j=1;j=n;j++) if((!s[j])(dist[j]temp)) {u=j;temp=dist[j];}//不在集合里，值《temp，选最小值 s[u]=true; for (j=1;j=n;j++) { if((!s[j])(c[u][j]MAX)) { int newdist=dist[u]+c[u][j]; if(newdistdist[j]){dist[j]=newdist;prev[j]=u;}//前驱u记录下来 } } } } void PrintPath(int *prev,int n,int begin,int end) { int *path=new int [n+1]; int i,m=n; bool k=true; path[end]=end; for(i=end-1;i1;i--) { path[i]=prev[path[i+1]]; //构造路径 m--; } for (i=m;i=end;i++) { coutpath[i]-; //输出路径 } cout\b\b endl; } void main() { int n,i; int v=1; cout请输入顶点个数：; cinn; int *dist=new int [n+1]; int *prev=new int [n+1]; int **c; c=new int *[n+1]; for (i=0;i=n;i++) {