资源描述:
《贪心算法和分支限界法解决单源最短路径.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、单源最短路径计科1班朱润华2012040732方法1:贪心算法一、贪心算法解决单源最短路径问题描述:单源最短路径描述:给定带权有向图G=(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称之为源(origin)。现在要计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到达路径各边权值之和。Dijkstra算法是解决单源最短路径问题的贪心算法。Dijkstra算法的基本思想是:设置顶点集合S并不断地做贪心选择来扩充集合。一个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。贪心扩充就
2、是不断在集合S中添加新的元素(顶点)。初始时,集合S中仅含有源(origin)一个元素。设curr是G的某个顶点,把从源到curr且中间只经过集合S中顶点的路称之为从源到顶点curr的特殊路径,并且使用数组distance记录当前每个顶点所对应的最短路径的长度。Dijkstra算法每次从图G中的(V-S)的集合中选取具有最短路径的顶点curr,并将curr加入到集合S中,同时对数组distance进行必要的修改。一旦S包含了所有的V中元素,distance数组就记录了从源(origin)到其他顶点的最短路径长度
3、。二、贪心算法思想步骤:Dijkstra算法可描述如下,其中输入带权有向图是G=(V,E),V={1,2,…,n},顶点v是源。c是一个二维数组,c[i][j]表示边(i,j)的权。当(i,j)不属于E时,c[i][j]是一个大数。dist[i]表示当前从源到顶点i的最短特殊路径长度。在Dijkstra算法中做贪心选择时,实际上是考虑当S添加u之后,可能出现一条到顶点的新的特殊路,如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i,则这种路的最短长度是dist[u]+c[u][i]。如果
4、dist[u]+c[u][i]上的权值。设S为已知最短路径的终点的集合,它的初始状态为空集。从源点v经过S到图上其余各点vi的当前最短路径长度的初值为:dist[i]=c[v][i],vi属于V;2、选择vu,使得dist[u]=Min{dist[i]
5、vi属于V-S},vj就是长度最短的最短路径的终点。令S=SU{u};3、修改从v到集合V-S上任一顶点vi的当前最短路径长度:如
6、果dist[u]+c[u][j]#include#include#includeusingnamespacestd;constintN=5;constintM=1000;ifstreamfin("4d5.txt");templatevoidDijkstra(intn,intv,
7、Typedist[],intprev[],Typec[][N+1]);voidTraceback(intv,inti,intprev[]);//输出最短路径v源点,i终点intmain(){intv=1;//源点为1intdist[N+1],prev[N+1],c[N+1][N+1];cout<<"有向图权的矩阵为:"<>c[i][j];cout<8、tra(N,v,dist,prev,c);for(inti=2;i<=N;i++){cout<<"源点1到点"<voidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]){bools[N+1];for(inti=1;i<=n;i++){dist[i]=c[v][i];//
9、dist[i]表示当前从源到顶点i的最短特殊路径长度s[i]=false;if(dist[i]==M){prev[i]=0;//记录从源到顶点i的最短路径i的前一个顶点}else{prev[i]=v;}}dist[v]=0;s[v]=true;for(inti=1;i