目的：
1、掌握分支限界法的基本思想；
2、掌握解决单源最短路径问题的分支限界法实现方法；
3、学会分析算法的时间复杂度；
4、学会用分支限界法解决实际问题。
要求：
1、输入带权图G=(V,E)以及出发顶点s，然后用分支限界法解决问题，要求输出路径和长度以及计算时间；
2、改变图中顶点和边的数量，分析运算时间的变化。
实验原理：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
实验代码：
#include
#include
#include
#include
#include
#include
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 pqu;
e.vno = v; //建立源点结点e（根结点）
e.length = 0;
pqu.push(e); //源点结点e进队
dist[v] = 0;
while (!pqu.empty()) //队列不空循环
{
e = pqu.front(); pqu.pop(); //出队列结点e
for (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的结点e1
e1.length = dist[j];
pqu.push(e1); //结点e1进队
}
}
}
}
void addEdge(int i, int j, int w) //图中添加一条边
{
cout<<"输入所有边的起点、终点和边长（用空格隔开）:"<> 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的最短路径
{
vectorpath;
if (v == i)return;
if (dist[i] == INF)
cout<<"从源点"<= 0; j--) //反向输出构成正向路径
cout<> 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;
}
实验结果:
