贪心算法和分支限界法解决单源最短路径(共9页)

1、精选优质文档-倾情为你奉上单源最短路径计科1班 朱润华 方法1：贪心算法一、 贪心算法解决单源最短路径问题描述：单源最短路径描述：给定带权有向图G=(V,E),其中每条边的权是非负实数。另外，还给定V中的一个顶点，称之为源(origin)。现在要计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到达路径各边权值之和。Dijkstra算法是解决单源最短路径问题的贪心算法。Dijkstra算法的基本思想是：设置顶点集合S并不断地做贪心选择来扩充集合。一个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。贪心扩充就是不断在集合S中添加新的元素（顶点）。初始时，集合S中仅含有源(orig

2、in)一个元素。设curr是G的某个顶点，把从源到curr且中间只经过集合S中顶点的路称之为从源到顶点curr的特殊路径，并且使用数组distance记录当前每个顶点所对应的最短路径的长度。Dijkstra算法每次从图G中的(V-S)的集合中选取具有最短路径的顶点curr，并将curr加入到集合S中，同时对数组distance进行必要的修改。一旦S包含了所有的V中元素，distance数组就记录了从源(origin)到其他顶点的最短路径长度。二、 贪心算法思想步骤：Dijkstra算法可描述如下，其中输入带权有向图是G=(V,E)，V=1,2,，n，顶点v是源。c是一个二维数组，cij表示边(

3、i,j)的权。当(i,j)不属于E时，cij是一个大数。disti表示当前从源到顶点i的最短特殊路径长度。在Dijkstra算法中做贪心选择时，实际上是考虑当S添加u之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i，则这种路的最短长度是distu+cui。如果distu+cui<disti，则需要更新disti的值。步骤如下： 1、用带权的邻接矩阵c来表示带权有向图, cij表示弧<vi,vj>上的权值。设S为已知最短路径的终点的集合,它的初始状态为空集。从源点v经过S到图上其余各点vi的当前最短路径长度的初值为

4、：disti=cvi, vi属于V； 2、选择vu, 使得distu=Mindisti | vi属于V-S,vj就是长度最短的最短路径的终点。令S=S U u；3、修改从v到集合V-S上任一顶点vi的当前最短路径长度:如果 distu+cuj< distj 则修改 distj= distu+cuj； 4、重复操作(2),(3)共n-1次。三、 算法实现代码：#include <stdafx.h>#include <iostream>#include <fstream>#include <string>using namespace std;

5、 const int N = 5;const int M = 1000;ifstream fin("4d5.txt"); template<class Type>void Dijkstra(int n,int v,Type dist,int prev,Type cN+1); void Traceback(int v,int i,int prev);/输出最短路径 v源点，i终点 int main() int v = 1;/源点为1 int distN+1,prevN+1,cN+1N+1; cout<<"有向图权的矩阵为："<

6、<endl; for(int i=1; i<=N; i+) for(int j=1; j<=N; j+) fin>>cij; cout<<cij<<" " cout<<endl; Dijkstra(N,v,dist,prev,c); for(int i=2; i<=N; i+) cout<<"源点1到点"<<i<<"的最短路径长度为:"<<disti<<"，其路径为" Tracebac

7、k(1,i,prev); cout<<endl; return 0; template<class Type> void Dijkstra(int n,int v,Type dist,int prev,Type cN+1) bool sN+1; for(int i=1; i<=n; i+) disti = cvi;/disti表示当前从源到顶点i的最短特殊路径长度 si = false; if(disti = M) previ = 0;/记录从源到顶点i的最短路径i的前一个顶点 else previ = v; distv = 0; sv = true; for(i

8、nt i=1; i<n; i+) int temp = M; int u = v;/上一顶点 /取出V-S中具有最短特殊路径长度的顶点u for(int j=1; j<=n; j+) if(!sj) && (distj<temp) u = j temp = distj; su = true; /根据作出的贪心选择更新Dist值 for(int j=1; j<=n; j+) if(!sj) && (cuj<M) Type newdist = distu + cuj; if(newdist < distj) distj = new

9、dist; prevj = u; /输出最短路径 v源点，i终点void Traceback(int v,int i,int prev) if(v = i) cout<<i; return; Traceback(v,previ,prev); cout<<"->"<<I; 四、计算复杂性 对于一个具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。算法的其余部分所需要的时间不超过O(n2)。五、 运行结果：方法2：

10、分支限界法一、 分支限界法解决单源最短路径问题描述：采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。二、 分支限界法算法思想描述：

11、算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路

12、长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。三、 算法实现代码：#include "stdafx.h" #include "MinHeap2.h" #include <iostream> #include <fstream> using namespace std; ifstream fin("6d2.txt"); template<class Type> class Graph friend int main(); public: void ShortesPaths(int);

13、 private: int n, /图G的顶点数 *prev; /前驱顶点数组 Type *c, /图G的领接矩阵 *dist; /最短距离数组 ; template<class Type> class MinHeapNode friend Graph<Type> public: operator int ()constreturn length; private: int i; /顶点编号 Type length; /当前路长 ; template<class Type> void Graph<Type>:ShortesPaths(int v)

14、/单源最短路径问题的优先队列式分支限界法 MinHeap<MinHeapNode<Type>> H(1000); MinHeapNode<Type> E; /定义源为初始扩展节点 E.i=v; E.length=0; distv=0; while (true)/搜索问题的解空间 for (int j = 1; j <= n; j+) if (cE.ij!=0)&&(E.length+cE.ij<distj) / 顶点i到顶点j可达，且满足控制约束 distj=E.length+cE.ij; prevj=E.i; / 加入活结点优先

15、队列 MinHeapNode<Type> N; N.i=j; N.length=distj; H.Insert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (int) break; if (H.currentsize=0)/ 优先队列空 break; int main() int n=11; int prev12 = 0,0,0,0,0,0,0,0,0,0,0,0; int dist12=1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000; cout<<"单

16、源图的邻接矩阵如下："<<endl; int *c = new int*n+1; for(int i=1;i<=n;i+) ci=new intn+1; for(int j=1; j<=n; j+) fin>>cij; cout<<cij<<" " cout<<endl; int v=1; Graph<int> G; G.n=n; G.c=c; G.dist=dist; G.prev=prev; G.ShortesPaths(v); cout<<"从S到T的最短路长是："<<dist11<<endl; for (int i = 2; i <= n; i+) cout<<"prev("<<i<<")="<<previ<<" "<<endl; for (int i = 2; i <