分支定界单源最短路径

单源最短路径单源最短路径在最短路径问题中，我们给定⼀个带权重的有向图和权重函数, 该权重函数将每条边映射到实数值的权重上。

图中⼀条路径的权重是构成该路径的所有边的权重之和：定义从结点u到结点v的最短路径权重如下：从结点u到结点v的最短路径则定义为任何⼀条权重为的从u到v的路径p。

最短路径的⼏个变体单源最短路径：给定⼀个图G=(V,E),我们希望找到从给定源结点到每个节点的最短路径。

单⽬的地最短路径问题：找到从每个节点u到给定⽬的地节点t的最短路径。

如果将图的每条边的⽅向翻转过来，我们就可以将这个问题转换为单源最短路径问题。

单节点对最短路径问题：找到从给定节点u到给定节点v的最短路径。

如果解决了针对单个节点u的单源最短路径问题，那么也就解决这个问题。

所有节点对最短路径问题：对于每个节点u和v，找到从结点u到结点v的最短路径。

虽然可以针对每节点运⾏⼀遍单源最短路径算法，但通常可以更快地解决这个问题。

初始化松弛操作Bellman-Ford算法topo sort有向⽆环图中的单源最短路径问题根据节点的拓扑排序次序对带权重的有向⽆环图G=(V,E)进⾏边的松弛操作，我们便可以在时间内计算出从单个源结点到所有节点之间的最短路径。

在有向⽆环图中，即使存在权重为负的边，但因为没有权重为负的环路，最短路径都是存在的。

算法⾸先对有向⽆环图进⾏拓扑排序，以便确定结点之间的⼀个线性次序。

以便确定结点之间的⼀个线性次序。

如果有向⽆环图包含从结点u到结点v的⼀条路径，则u的拓扑排序的次序中位于结点v的前⾯。

我们只需要按照拓扑排序的次序对结点进⾏⼀遍处理即可。

每次对⼀个节点进⾏处理时，我们对从该节点发出的发出的所有的边进⾏松弛操作。

Dijkstra算法三个算法的对⽐所有节点对的最短路径问题Floyd-Warshall算法//基本思想是：//进⾏中转......允许经过1~n号所有顶点进⾏中转，求任意两点之间的最短路程。

//⽤⼀句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY算法设计与分析实验报告实验项目实验五实验类别验证性学生姓名王龙学生学号201400797 完成日期2016-5-6指导教师刘振章实验成绩评阅日期评阅教师刘振章实验五：分枝限界法【实验目的】应用分枝限界法的算法设计思想求解单源最短路径问题。

【实验性质】验证性实验。

【实验内容与要求】采用分支限界法编程求源点0到终点6的最短路径及其路径长度。

要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。

【算法思想及处理过程】由于要找的是从源到各顶点的最短路径，所以选用一个数组存起来.Fenzhi函数: 由于先前赋值时, 用一个二维数组将结点的有向图标记存起来了( 有边为1, 无边为0 ),并且又用另外一个二维数组将其权重存起来了; 首先, 通过双重for循环, 通过if语句判断, 如果标记为1, 并且相加的权重小于先前最优权重( 在初始化的时候, 对最优权重赋上一个最大值 ), 则求得最优权重, 并且用一维数组将权重存起来, 而且用一维数组将前驱结点存起来.你然后, 一直循环下去, 直到循环到目的结点.【程序代码】for (z=0; z<k; z++){scanf ("%d %d %d", &i, &j, &m);t[i][j] = m;ti[i][j] = 1;}for (i = 0; i < n; i++) //初始化数组{d[i] = 99; // 赋个最大值s[i] = -1;}}void fenzhi (int d[], int s[],int t[][MAX], int ti[][MAX], int n, int k) {int i, j, zi;d[0]=0; s[0]=-1;for (i=0; i<n; i++){printf ("当前扩展节点：%d，权重：%d : \n", i, d[i]);for (j=0; j<n; j++){if (ti[i][j] == 1 ){if ( d[j]>t[i][j]+d[i]){d[j]=t[i][j]+d[i]; //最短长度s[j]=i; //前驱结点}if (j != n /* && j != 6 */ )printf ("入队结点：%d ,最优权重：%d \n", j, d[j]);}}printf ("\n");}}void output (int d[], int s[], int n){int i, j=0, zi[MAX];printf ("从源点到各个结点的最短路径: \n");for (i=0; i<n; i++)printf ("dist[%d] = %d \n", i, d[i]);printf ("\n");printf ("从源点到终点的最短路径长度为: %d \n", d[n-1]);printf ("其路径为: %d ", n-1);zi[j] = s[n-1];printf ("----> %d ", zi[j]);while (zi[j] != 0){j++;zi[j] = s[zi[j-1]];printf ("----> %d ", zi[j]);}printf ("\n");}【运行结果】图1 输入数据图2 输出扩展结点图3 最终结果【算法分析】本程序的主要函数ShorestPaths的时间复杂度为: O ( n * (n-1) ), 最坏时间复杂度为: O ( n*n )【实验总结】。

单源最短路径计科1班朱润华2012040732方法1：贪心算法一、贪心算法解决单源最短路径问题描述：单源最短路径描述：给定带权有向图G=(V,E),其中每条边的权是非负实数。

另外，还给定V中的一个顶点，称之为源(origin)。

现在要计算从源到其他各顶点的最短路径的长度。

这里的路径长度指的是到达路径各边权值之和。

Dijkstra算法是解决单源最短路径问题的贪心算法。

Dijkstra算法的基本思想是：设置顶点集合S并不断地做贪心选择来扩充集合。

一个顶点属于集合S当且仅当从源点到该顶点的最短路径长度已知。

贪心扩充就是不断在集合S中添加新的元素（顶点）。

初始时，集合S中仅含有源(origin)一个元素。

设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是一个二维数组，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]。

如果dist[u]+c[u][i]<dist[i]，则需要更新dist[i]的值。

分⽀限界法实验（单源最短路径）算法分析与设计实验报告第七次实验基本思想：附录：完整代码（分⽀限界法）Shorest_path.cpp//单源最短路径问题分⽀限界法求解#include#include#include#include"MinHeap2.h"using namespace std;templateclass Graph //定义图类{friend int main();public:void shortest_path(int); private:int n, //图的顶点数*prev; //前驱顶点数组Type **c, //图的邻接矩阵*dist; //最短距离数组};templateclass MinHeapNode //最⼩堆中的元素类型为MinHeapNode{friend Graph;public:operator int() const{return length;}private:int i; //顶点编号Type length; //当前路长};//单源最短路径问题的优先队列式分⽀限界法templatevoid Graph::shortest_path(int v){MinHeap> H(1000);//定义最⼩堆的容量为1000//定义源为初始扩展结点MinHeapNode E;//初始化源结点E.i=v;E.length=0;dist[v]=0;while(true)//搜索问题的解空间{for(int j=1;j<=n;j++)if((c[E.i][j]!=0)&&(E.length+c[E.i][j]{//顶点i到顶点j可达，且满⾜控制约束//顶点i和j之间有边，且此路径⼩于原先从源点i到j的路径长度dist[j]=E.length+c[E.i][j];//更新dist数组prev[j]=E.i;//加⼊活结点优先队列MinHeapNode N;N.i=j;N.length=dist[j];H.Insert(N);//插⼊到最⼩堆中}try{H.DeleteMin(E); // 取下⼀扩展结点}catch (int){break;}if(H.currentsize==0)//优先队列空{break;}}}int main(){int n=11;int prev[12]={0,0,0,0,0,0,0,0,0,0,0,0};//初始化前驱顶点数组intdist[12]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000};//初始化最短距离数组cout<<"单源图的邻接矩阵如下："<int **c=new int*[n+1];for(int i=1;i<=n;i++) //输⼊图的邻接矩阵{c[i]=new int[n+1];for(int j=1;j<=n;j++){cin>>c[i][j];}}int v=1; //源结点为1Graph G;G.n=n;G.c=c;G.dist=dist;G.prev=prev;clock_t start,end,over; //计算程序运⾏时间的算法start=clock();end=clock();over=end-start;start=clock();G.shortest_path(v);//调⽤图的最短路径查找算法//输出从源结点到⽬的结点的最短路径cout<<"从S到T的最短路长是："<for(int i=2;i<=n;i++)//输出每个结点的前驱结点{cout<<"prev("<}for(int i=2;i<=n;i++) //输出从源结点到其他结点的最短路径长度{cout<<"从1到"<}for(int i=1;i<=n;i++) //删除动态分配时的内存{delete[] c[i];}delete[] c;c=0;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显⽰运⾏时间cout< system("pause");return 0;}MinHeap.h#includetemplateclass Graph;templateclass MinHeap //最⼩堆类{templatefriend class Graph;public:MinHeap(int maxheapsize=10); //构造函数，堆的⼤⼩是10~MinHeap(){delete[] heap;} //最⼩堆的析构函数int Size() const{return currentsize;} //Size()返回最⼩堆的个数T Max(){if(currentsize) return heap[1];} //第⼀个元素出堆MinHeap& Insert(const T& x); //最⼩堆的插⼊函数MinHeap& DeleteMin(T& x); //最⼩堆的删除函数void Initialize(T x[],int size,int ArraySize); //堆的初始化void Deactivate();void output(T a[],int n);private:int currentsize,maxsize;T *heap;};templatevoid MinHeap::output(T a[],int n) //输出函数，输出a[]数组的元素{for(int i=1;i<=n;i++)cout<cout<}templateMinHeap::MinHeap(int maxheapsize){maxsize=maxheapsize;heap=new T[maxsize+1]; //创建堆currentsize=0;}templateMinHeap& MinHeap::Insert(const T& x){if(currentsize==maxsize) //如果堆中的元素已经等于堆的最⼤⼤⼩return *this; //那么不能在加⼊元素进⼊堆中int i= ++currentsize;while(i!=1 && x{heap[i]=heap[i/2];i/=2;}heap[i]=x;return *this;}templateMinHeap& MinHeap::DeleteMin(T& x) //删除堆顶元素{if(currentsize==0){cout<<"Empty heap!"<return *this;}x=heap[1];T y=heap[currentsize--];int i=1,ci=2;while(ci<=currentsize){if(ciheap[ci+1])ci++;if(y<=heap[ci])break;heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return *this;}templatevoid MinHeap::Initialize(T x[],int size,int ArraySize) //堆的初始化{ delete[] heap;heap=x;currentsize=size;maxsize=ArraySize;for(int i=currentsize/2;i>=1;i--){T y=heap[i];int c=2*i;while(c<=currentsize){if(cheap[c+1])c++;if(y<=heap[c])break;heap[c/2]=heap[c];c*=2;}heap[c/2]=y;}}templatevoid MinHeap::Deactivate() {heap=0;}。

算法分析与设计实验报告分支限界法实现单源最短路径班级：11计算机1学号：110104200109姓名：金李扬日期： 5.221.问题描述以分支限界法实现单源最短路径1.以分支限界实现优先队列2.再以分支限界法的优先队列实现单元最短路径以该图为算法测试数据，获得链接矩阵如下：以-1代表无法到达的点-1 2 3 4 -1 -1 -1 -1 -1 -1 -1-1 -1 3 -1 7 2 -1 -1 -1 -1 -1-1 -1 -1 -1 -1 9 2 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1-1 -1 -1 -1 -1 -1 -1 3 3 -1 -1-1 -1 -1 -1 -1 -1 1 -1 3 -1 -1-1 -1 -1 -1 -1 -1 -1 -1 5 1 -1-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -12.算法思想分支限界法基本思想：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

算法步骤1.用一极小堆来存储活结点表，其优先级是结点所对应的当前路长。

2.算法从图G的源顶点s和空优先队列开始。

结点s被扩展后，它的儿子结点被依次插入堆中。

此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。

分支限界法最短路径
分支限界法是一种常用于求解优化问题的算法，在寻找最短路径问题中也可以使用分支限界法进行求解。

最短路径问题是指在给定的有向图中，从起点出发到达终点的最短路径。

分支限界法通过建立搜索树，每个节点表示当前搜索的状态，通过扩展节点并计算估价函数来选择下一个搜索节点，最终找到最优解。

在最短路径问题中，我们可以将搜索树的每个节点表示为当前所在节点和到达该节点的路径长度。

每次扩展节点时，我们计算该节点到终点的估价函数，选择估价函数最小的节点进行扩展。

当找到终点时，即为最短路径。

需要注意的是，估价函数的选择会影响算法的效率和正确性。

对于最短路径问题，常用的估价函数包括欧几里得距离、曼哈顿距离等。

总之，分支限界法是一种求解最短路径问题的有效算法，可以在较短的时间内找到最优解。

在实际应用中，可以根据具体情况选择不同的估价函数来提高算法的效率。

- 1 -。

算法分析与设计实验报告第七次实验姓名学号班级时间12.26上午地点工训楼309实验名称分支限界法实验(单源最短路径)实验目的1.掌握并运用分支限界法的基本思想2.运用分支限界法实现单源最短路径问题实验原理问题描述：在下图所给的有向图G中，每一边都有一个非负边权。

要求图G的从源顶点s 到目标顶点t之间的最短路径。

基本思想：下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。

其中，每一个结点旁边的数字表示该结点所对应的当前路长。

为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。

按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。

catch (int){break;}if(H.currentsize==0) //优先队列空{break;}}}上述有向图的结果：测试结果附录：完整代码（分支限界法）Shorest_path.cpp//单源最短路径问题分支限界法求解#include<iostream>#include<time.h>#include<iomanip>#include"MinHeap2.h"using namespace std;template<class Type>class Graph //定义图类{friend int main();public:void shortest_path(int); private:int n, //图的顶点数*prev; //前驱顶点数组Type **c, //图的邻接矩阵*dist; //最短距离数组};template<class Type>class MinHeapNode //最小堆中的元素类型为MinHeapNode{friend Graph<Type>;public:operator int() const{return length;}private:int i; //顶点编号Type length; //当前路长};//单源最短路径问题的优先队列式分支限界法template<class Type>void Graph<Type>::shortest_path(int v){MinHeap<MinHeapNode<Type>> H(1000);//定义最小堆的容量为1000//定义源为初始扩展结点MinHeapNode<Type> E;//初始化源结点E.i=v;E.length=0;dist[v]=0;while(true)//搜索问题的解空间{for(int j=1;j<=n;j++)if((c[E.i][j]!=0)&&(E.length+c[E.i][j]<dist[j])){//顶点i到顶点j可达，且满足控制约束//顶点i和j之间有边，且此路径小于原先从源点i到j的路径长度dist[j]=E.length+c[E.i][j];//更新dist数组prev[j]=E.i;//加入活结点优先队列MinHeapNode<Type> N;N.i=j;N.length=dist[j];H.Insert(N);//插入到最小堆中}try{H.DeleteMin(E); // 取下一扩展结点}catch (int){break;}if(H.currentsize==0)//优先队列空{break;}}}int main(){int n=11;int prev[12]={0,0,0,0,0,0,0,0,0,0,0,0};//初始化前驱顶点数组intdist[12]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000 };//初始化最短距离数组cout<<"单源图的邻接矩阵如下："<<endl;int **c=new int*[n+1];for(int i=1;i<=n;i++) //输入图的邻接矩阵{c[i]=new int[n+1];for(int j=1;j<=n;j++){cin>>c[i][j];}}int v=1; //源结点为1Graph<int> G;G.n=n;G.c=c;G.dist=dist;G.prev=prev;clock_t start,end,over; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();G.shortest_path(v);//调用图的最短路径查找算法//输出从源结点到目的结点的最短路径cout<<"从S到T的最短路长是："<<dist[11]<<endl;for(int i=2;i<=n;i++)//输出每个结点的前驱结点{cout<<"prev("<<i<<")="<<prev[i]<<" "<<endl;}for(int i=2;i<=n;i++) //输出从源结点到其他结点的最短路径长度{cout<<"从1到"<<i<<"的最短路长是："<<dist[i]<<endl;}for(int i=1;i<=n;i++) //删除动态分配时的内存{delete[] c[i];}delete[] c;c=0;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间cout<<endl;system("pause");return 0;}MinHeap.h#include<iostream>template<class Type>class Graph;template<class T>class MinHeap //最小堆类{template<class Type>friend class Graph;public:MinHeap(int maxheapsize=10); //构造函数，堆的大小是10~MinHeap(){delete[] heap;} //最小堆的析构函数int Size() const{return currentsize;} //Size()返回最小堆的个数T Max(){if(currentsize) return heap[1];} //第一个元素出堆MinHeap<T>& Insert(const T& x); //最小堆的插入函数MinHeap<T>& DeleteMin(T& x); //最小堆的删除函数void Initialize(T x[],int size,int ArraySize); //堆的初始化void Deactivate();void output(T a[],int n);private:int currentsize,maxsize;T *heap;};template<class T>void MinHeap<T>::output(T a[],int n) //输出函数，输出a[]数组的元素{for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;}template<class T>MinHeap<T>::MinHeap(int maxheapsize){maxsize=maxheapsize;heap=new T[maxsize+1]; //创建堆currentsize=0;}template<class T>MinHeap<T>& MinHeap<T>::Insert(const T& x){if(currentsize==maxsize) //如果堆中的元素已经等于堆的最大大小return *this; //那么不能在加入元素进入堆中int i= ++currentsize;while(i!=1 && x<heap[i/2]){heap[i]=heap[i/2];i/=2;}heap[i]=x;return *this;}template<class T>MinHeap<T>& MinHeap<T>::DeleteMin(T& x) //删除堆顶元素{if(currentsize==0){cout<<"Empty heap!"<<endl;return *this;}x=heap[1];T y=heap[currentsize--];int i=1,ci=2;while(ci<=currentsize){if(ci<currentsize && heap[ci]>heap[ci+1])ci++;if(y<=heap[ci])break;heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return *this;}template<class T>void MinHeap<T>::Initialize(T x[],int size,int ArraySize) //堆的初始化{delete[] heap;heap=x;currentsize=size;maxsize=ArraySize;for(int i=currentsize/2;i>=1;i--){T y=heap[i];int c=2*i;while(c<=currentsize){if(c<currentsize && heap[c]>heap[c+1])c++;if(y<=heap[c])break;heap[c/2]=heap[c];c*=2;}heap[c/2]=y;}}template<class T>void MinHeap<T>::Deactivate(){heap=0; }。

一．分支界限法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

对已处理的各结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值（极大/极小）的结点优先进行广度优先搜索 不断调整搜索方向，尽快找到解。

特点：限界函数常基于问题的目标函数，适用于求解最优化问题。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

二．单源最短路径问题1.问题描述下面以一个例子来说明单源最短路径问题：在下图所给的有向图G 中，每一边都有一个非负边权。

要求图G的从源顶点s到目标顶点t 之间的最短路径。

下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。

其中，每一个结点旁边的数字表示该结点所对应的当前路长。

2. 算法思想解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。

其优先级是结点所对应的当前路长。

算法从图G的源顶点s和空优先队列开始。

结点s被扩展后，它的儿子结点被依次插入堆中。

此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。

如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

这个结点的扩展过程一直继续到活结点优先队列为空时为止。

3. 剪枝策略在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。

在算法中，利用结点间的控制关系进行剪枝。

从源顶点s出发，2条不同路径到达图G的同一顶点。