目的：
1、掌握分支限界法的基本思想；
2、掌握解决单源最短路径问题的分支限界法实现方法；
3、学会分析算法的时间复杂度；
4、学会用分支限界法解决实际问题。
要求：
1、输入带权图G=(V,E)以及出发顶点s，然后用分支限界法解决问题，要求输出路径和长度以及计算时间；
2、改变图中顶点和边的数量，分析运算时间的变化。
实验原理：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
实验代码：
#include<iostream>#include<stdio.h>#include<string.h>#include<queue>#include<vector>#include <time.h>using namespace std;#define INF 0x3f3f3f3f //表示∞#define MAXN 51//问题表示int dingdian; //图顶点个数int a[MAXN][MAXN];//图的邻接矩阵int v;//源点int b;//求解结果表示int dist[MAXN];//dist[i]源点到顶点i的最短路径长度int prev_one[MAXN]; //prev[i]表示源点到j的最短路径中顶点j的前驱顶点struct NodeType//队列结点类型{int vno;//顶点编号int length;//路径长度};void bfs(int v)//求解算法{NodeType e, e1;queue<NodeType> pqu;e.vno = v;//建立源点结点e（根结点）e.length = 0;pqu.push(e);//源点结点e进队dist[v] = 0;while (!pqu.empty())//队列不空循环{e = pqu.front(); pqu.pop();//出队列结点efor (int j = 0; j < dingdian; j++){if (a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j]){//剪枝：e.vno到顶点j有边并且路径长度更短dist[j] = e.length + a[e.vno][j];prev_one[j] = e.vno;e1.vno = j;//建立相邻顶点j的结点e1e1.length = dist[j];pqu.push(e1);//结点e1进队}}}}void addEdge(int i, int j, int w)//图中添加一条边{cout<<"输入所有边的起点、终点和边长（用空格隔开）:"<<endl;for (int q = 0; q < b; q++){cin >> i >> j >> w;if (i >= dingdian || j >= dingdian){cout << "添加失败，错误的边" << endl;cout << "你还可以再输入" << b - q << "条边" << endl;q = q - 1;}a[i][j] = w;}}void dispapath(int v, int i) //输出从V到I的最短路径{vector<int>path;if (v == i)return;if (dist[i] == INF)cout<<"从源点"<<v<<"到顶点"<<i<<"没有路径"<<endl;else {int k = prev_one[i];path.push_back(i); //添加目标顶点while (k != v) //添加中间顶点{path.push_back(k);k = prev_one[k]; }path.push_back(v);//添加源点printf("从源点%d到顶点%d的最短路径长度:%d,路径:", v, i, dist[i]);for (int j = path.size() - 1; j >= 0; j--)//反向输出构成正向路径cout<<path[j]<<" ";printf("\n");}}void dispallpath(int v) //输出从源点v出发的所有最短路径{for (int i = 0; i < dingdian; i++)dispapath(v, i);}int main(){memset(dist, INF, sizeof(dist)); //初始化为∞memset(a, INF, sizeof(a)); //初始化为∞cout << "输入顶点个数和边数：";cin >> dingdian>>b; //有向图的顶点个数cout << "顶点名称为：";for (int i = 0; i < dingdian; i++){cout << i << " ";}cout << endl;for (int i = 0; i < dingdian; i++)a[i][i] = 0;int m = 0;int n = 0; int w = 0;addEdge(m, n, w);cout << "输入出发源点：";cin >> v;bfs(v);printf("求解结果\n");dispallpath(v);cout << "运行时间:" << (double)clock() / CLOCKS_PER_SEC << "ms" << endl;return 0;}
实验结果:
【算法设计与分析】分支限界法解决单源最短路径问题:输入带权图G=(V E)以及出发顶点s 然后用分支限界法解决问题 要求输出路径和长度以及计算时间；
