《01二班侯健夫02.docVIP

单源最短路径 二班 侯健夫 2012090490 贪心算法求单源最短路径： 一，问题描述： 给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 二．问题分析，推导过程： 最优子结构即可用来寻找整个问题最优解的子问题的最优解。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提 举例来说，寻找图上某顶点到终点的最短路径，可先计算该顶点所有相邻顶点至终点的最短路径，然后以此来选择最佳整体路径，如图1所示。 一般而言，最优子结构通过如下三个步骤解决问题： a) 将问题分解成较小的子问题； b) 通过递归使用这三个步骤求出子问题的最优解； c) 使用这些最优解构造初始问题的最优解。 子问题的求解是通过不断划分为更小的子问题实现的，直至我们可以在常数时间内求解，在我下面第一种算法中就是利用贪心算法局部最优化，然后再所有的可能性中找出最短的路径从而达到整体最优。 三．计算求解过程、算法实现（源代码实现相关功能）： #include stdio.h #define N 6 #define maxint 200 main() { void dijkstra(int n,int v,int dist[],int prev[],int c[][]); void path1(int prev[],int v); int c[6][6]={{0,0,0,0,0,0}, {0,0,10,maxint,30,100}, {0,maxint,0,50,maxint,maxint}, {0,maxint,maxint,0,maxint,10}, {0,maxint,maxint,20,0,60}, {0,maxint,maxint,maxint,maxint,0}};//设定6*6数组并赋值 int dist[6]={0},prev[6]={0}; int n=N-1,v=1; int i,j; /*for(i=1;i=n;i++) for(j=1;j=n;j++) scanf(%d,c[i][j]);*/ dijkstra(n,v,dist,prev,c); /*for(i=1;i=n;i++) printf(%5d,dist[i]); printf(\n);*/ //从源点开始向下一节点走，并得到距离 path1(prev,v); getch(); } void dijkstra(int n,int v,int dist[6],int prev[6],int c[6][6]){ int s[6]; int i,j,u,temp,newdist; for(i=1;i=n;i++){ dist[i]=c[v][i]; s[i]=0; if(dist[i]==maxint) prev[i]=0; else prev[i]=v; }//利用dist记录到每个节点的最短路径并做贪心选择 dist[v]=0; s[v]=1; for(i=1;i=n-1;i++){ temp=maxint; u=v; for(j=1;j=n;j++) if((!s[j])(dist[j]temp)){u=j;temp=dist[j];} s[u]=1; printf(\nu=%d,u); for(j=1;j=n;j++){ if((!s[j])(c[u][j]maxint)){ newdist=dist[u]+c[u][j]; if(newdistdist[j]){dist[j]=newdist;prev[j]=u;} } printf(%5d,%3d,dist[j],prev[j]);} }printf(\n); }//得到距离并且输出 void path1(int prev[],int v){ int stack[N]; int i1,i2,j,k; for(i1=1;i1=N-1;i1++){ if(i1!=v)