贪心算法和分支限界法解决单源最短路径.doc

《贪心算法和分支限界法解决单源最短路径.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