《单源最短路径.docxVIP

单源最短路径13计科行知班 张志超 2013020051一 问题描述给定带权有向图G=（V，E），其中每条边的的权都是非负实数。另外，还给定V中的一个顶点称为源。现在要计算源到其他所有顶点的最短路径长度，这里的路径长度指的是路上各边权之和。贪心算法 问题分析和推导过程（1）问题分析为甚想到了用贪心算法？从解决该问题的方法来看解决该问题的过程就是不断选择最优路径所需要经过的顶点，然后解决选取完相应顶点所产生的子问题的过程，这与贪心算法不谋而合，，而且此问题的解还具有贪心算法的最优子结构性质。（2）推导过程对于单元最短路径问题，在数据结构的课程中有过详细的介绍，我们知道解决此问题解决方法称为dijkstra算法，下面介绍该算法的基本思想，设置定点集合S并不断的做贪心选择来扩充这个集合。一个定点数与集合s当且仅当从源到该顶点的最短路径已知。初始时，s中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过 S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度，dijstra算法每次从V-S中取出具有最短特殊路径长度的顶点u，将u添加到s中，同时对数组dist进行必要的修改，一旦S包含了所有V的所有顶点那么S终究记录了源到其他所有顶点之间的最短路径。最优子结构性质证明欲证明最优子结构性质只要考察算法中子啊添加u到s后，dist[u]的值所起的变化。将添加u之前的S称为老S当添加了u之后，可能出现一条到达顶点i的新路径，。如果这条新路径事先经过老S到达顶点u，然后从u经一条边直接到达顶点i。则这种路的最短长度为dist[u]+a[u][i] 。这时若dist[u]+a[u][i]dist[i],则算法中用dist[u]+a[u][i]作为dist[i]的新值。若不是从u经过一条边直接到达i而是回到老S中某个顶点x，那么由于x在老S中，所以u比x早加入s所以从源到X的长度比从源点到U,再从U到X路径短，故不需考虑.所以无论dist[u]是否有变化，总是关于定点集S到顶点U的最短特殊路径长度三 算法实现Dijistra算法可描述如下。其中输入带权有向图是G=（V,E），V = {1,2,…….,n}。顶点V是源。a是一个二维数组,a[i][j]表示边（i.j）的权。当（i，j）是一个大数。Dist[i]表示当前从源到顶点i的最短特殊路径长度。Public static void dijstra(int v, float[][] a,float [] dist, int [] prev){ Int n= dist.length-1; If(v1 || vn) return ; boolean [][] s = new booolean[n+1]; for(int i = 1; in;i++){ dist[i] = a[v][i]; s[i] = false ; if(dist [j] == float.MAX_VALUE) prev[i] = 0; else prev[i] = v;}dist[v] = 0;s[v] = true;for(int I = 1; i n; i++){ Float temp = FLOAT.MAX_VALUE; Int u = v;For(int j = 1; j n; j++){ If((!s[j])(a[u][jfloatMAX_VALUE])){ float newdist = dist[u]+a[u][j]; if(newdist dist[j]) { Dist[j] = newdist; Prev[j] = u; } }}}程序全部代码如下:#include?iostream#includestack#define?M?100#define?N?100using?namespace?std;typedef?struct?node{?int?matrix[N][M];??????//邻接矩阵??int?n;?????????????????//顶点数??int?e;?????????????????//边数?}MGraph;?void?DijkstraPath(MGraph?g,int?*dist,int?*path,int?v0) 0表示源顶点?{?int?i,j,k;?bool?*visited=(bool?*)malloc(sizeof(bool)*g.n);?for(i=0;ig.n;i++)?????//初始化??{?if(g.matrix[v0][i]0i!=v0)?{?dist[i]=g.matrix[v0][i];?path[i]=v0;?????//path记录最短路径上从v0到i的前一个顶点??}?else?{?dist[i]=INT_MAX;?