《贪心算法和分支限界法解决单源最短路径》由会员分享，可在线阅读，更多相关《贪心算法和分支限界法解决单源最短路径（7页珍藏版）》请在金锄头文库上搜索。
1、贪心算法和分支限界法解决单源最短路径单源最短路径计科 1 班 朱润华 *-*32方法 1：贪心算法一、贪心算法解决单源最短路径问题描述：单源最短路径描述：给定带权有向图G=(V,E)，其中每条边的权是 非负实数。另外，还给定V中的一个顶点，称之为源(origin)。现在要 计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到 达路径各边权值之和。Dijkstra算法是解决单源最短路径问题的贪心算法。Dijkstra算法 的基本思想是：设置顶点集合 S 并不断地做贪心选择来扩充集合。一 个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。贪 心扩充就是不断在集合S中添加新的元素(顶
2、点)。初始时，集合S中仅含有源(origin)个元素。设curr是G的某 个顶点，把从源到 curr 且中间只经过集合 S 中顶点的路称之为从源 到顶点curr的特殊路径，并且使用数组distance记录当前每个顶点 所对应的最短路径的长度。Dijkstra算法每次从图G中的(V-S)的集合 中选取具有最短路径的顶点curr，并将curr加入到集合S中，同时对 数组 distance 进行必要的修改。一旦 S 包含了所有的 V 中元素， distance数组就记录了从源(origin)到其他顶点的最短路径长度。二、贪心算法思想步骤：Dijkstra 算法可描述如下，其中输入带权有向图是 G=(
3、V,E)， V二12?，n，顶点v是源。c是一个二维数组，cij表示边(i,j)的权。 当(i,j)不属于E时，cij是一个大数。disti表示当前从源到顶点i的 最短特殊路径长度。在 Dijkstra 算法中做贪心选择时，实际上是考虑 当 S 添加 u 之后，可能出现一条到顶点的新的特殊路，如果这条新特 殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点i, 则这种路的最短长度是 distu+cui。如果 distu+cuidisti, 则需要更新disti的值。步骤如下：1、用带权的邻接矩阵c来表示 带权有向图,cij表示弧 上的权值。设S为已知最短路径的 终点的集合,它的初始状
4、态为空集。从源点v经过S到图上其余各点 vi的当前最短路径长度的初值为: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 #include #include #include using namespace std; const int N = 5; const
5、 int M = 1000;ifstream fin(template void Dijkstra(int n,int v,Type dist,int prev,Type cN+1); voidTraceback(int v,int i,int prev);输出最短路径 v 源点，i 终点int main() int v = 1;/源点为 1int distN+1,prevN+1,cN+1N+1;cout有向图权的矩阵为： for(int i=1; i i+) for(int j=1; j j+) fincij; cout coutendl; Dijkstra(N,v,dist,prev,c)
6、;for(int i=2; i i+) cout 源 点 1 到 点 的最短路径长度为 :，其路径为 Traceback(1,i,prev); coutendl; return 0; template void Dijkstra(int n,int v,Type dist,int prev,Type cN+1) bool sN+1;for(int i=1; i i+) disti = cvi;/disti表示当前从源到顶点i的最短特殊路径长度 si = false;if(disti = M) previ = 0;/记录从源到顶点 i 的最短路径 i 的前一个顶点 else previ = v;
7、 distv = 0; sv = true;for(int i=1; in; i+) int temp = M; int u = v; 上一顶点取出V-S中具有最短特殊路径长度的顶点u for(int j = 1; j j +) if(!sj) (distjtemp) u = jtemp = distj; su = true;根据作出的贪心选择更新Dist值for(int j = 1; j j +) if(!sj)(cujm) Type newdist = distu + cuj; if(newdist distj) distj = newdist; prevj = u; 输出最短路径v源点，
8、i终点void Traceback(int v,int i,int prev) if(v = i) cout return; Traceback(v,previ,prev); cout四、计算复杂性对于一个具有n个顶点和e条边的带权有向图，如果用带权邻接 矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个 循环需要执行n-1次，所以完成循环需要O(nA2)时间。算法的其余 部分所需要的时间不超过O(n2)o五、运行结果：方法 2：分支限界法一、分支限界法解决单源最短路径问题描述： 采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。所谓“分支”是采用广度
9、优先的策略，依次生成扩展结 点的所有分支(即：儿子结点)。所谓“限界是在结点扩展过程中，计 算结点的上界(或下界)，边搜索边减掉搜索树的某些分支，从而提 高搜索效率按照广度优先的原则，一个活结点一旦成为扩展结点(E-结点) R 后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导 致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点 表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至 找到问题的解或判定无解为止。二、分支限界法算法思想描述：算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它 的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路 长的结点作为
10、当前扩展结点，并依次检查与当前扩展结点相邻的所有 顶点。如果从当前扩展结点 i 到顶点 j 有边可达，且从源出发，途经 顶点 i 再到顶点 j 的所相应的路径的长度小于当前最优路径长度，则 将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程 一直继续到活结点优先队列为空时为止。在算法扩展结点的过程中， 一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以 该结点为根的子树。在算法中，利用结点间的控制关系进行剪枝。从源顶点 s 出发， 2 条不同路径到达图 G 的同一顶点。由于两条路径的路长不同，因此 可以将路长长的路径所对应的树中的结点为根的子树剪去。三、算法实现代码： #i
11、nclude #include #include #include using namespace std; ifstream fin(template class Graph friend int main();public:void ShortesPaths(int);private:int n, /图 G 的顶点数 *prev; /前驱顶点数组 Type *c, /图 G 的 领接矩阵 *dist; /最短距离数组 ;template class MinHeapNode friend Graph ; public: operator int ()constreturn length; p
12、rivate:int i; /顶点编号 Type length; /当前路长 ;template void Graph:ShortesPaths(int v) 单源最短路径问题的优先队列式分支限界法 MinHeapH(1000);MinHeapNodeE; /定义源为初始扩展节点 E.i=v;E.length=0; distv=0;while (true)/搜索问题的解空间for (int j = 1; j j+)if (cE.ij!=0)(E.length+cE.ijdistj) / 顶点 i 到顶点 j 可达，且满足控制约束 distj=E.length+cE.ij; prevj=E.i;
13、/ 加入活结点优先队列 MinHeapNode N; N.i=j; N.I ength二distj; H.lnsert(N); try H.DeleteMin(E); / 取下一扩展结点 catch (int) break;if (H.currentsize=0)/ 优先队列空 break; int main()int n=11;int prev = 0,0,0,0,0,0,0,0,0,0,0,0;intdist=1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,100 0;cout单源图的邻接矩阵如下： int *c = new int*n + 1;for(int i=1;ii+) ci=new intn+1; for(int j=1; j j+) fincij; cout /cij
