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