实验五 分支限界法实现单源最短路径
一 实验题目：分支限界法实现单源最短路径问题
二 实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。
三 实验
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。
四 实验代码
#include
using namespace std;
const int size = 100;
const int inf = 5000; //两点距离上界
const int n = 6; //图顶点个数加1
int prev[n]; //图的前驱顶点
int dist[] = {0,0,5000,5000,5000,5000}; //最短距离数组
int c[n][n] = {{0,0,0,0,0,0},{0,0,2,3,5000,5000}, //图的邻接矩阵
{0,5000,0,1,2,5000},{0,5000,5000,0,9,2},
{0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}};
const int n = 5; //图顶点个数加1
int prev[n]; //图的前驱顶点
int dist[] = {0,0,5000,5000,5000};
int c[][n] = {{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,2},{0,5000,5000,0,9},{0,5000,5000,5000,0}};
class MinHeapNode
{
public :
int i; //顶点编号
int length; //当前路长
};//循环队列
class CirQueue{
private:
int front,rear;
MinHeapNode data[size];
public:
CirQueue(){
front = rear = 0;
}//元素入队操作
void queryIn(MinHeapNode e){
if((rear +1)%size != front){
rear = (rear+1)%size; //队尾指针在循环意义下加1
data[rear] = e; //在队尾插入元素
}
}//元素出队操作
MinHeapNode queryOut(){
if(rear != front){
front = (front+1)%size; //队列在循环意义下加1
return data[front];
}
} //读取队头元素，但不出队
MinHeapNode getQuery(){
if(rear != front)
{
return data[(front+1)%size];
}
} //判断队列是否为空
bool empty()
{
return front == rear;
} //判断队列是否为满
bool full()
{
return (rear +1)%size == front;
}
};//CirQueue结束
class Graph{
public:
/**
* 单源最短路径问题的优先队列式分支限界法
*/
void shortestPath(int v)
{
CirQueue qq;//定义源为初始扩展结点
MinHeapNode e;
e.i = v;
e.length = 0;
dist[v] = 0;
qq.queryIn(e); //搜索问题的解空间
while(true){
for(int j = 1;j=n)
{
break;
}
MinHeapNode m = qq.getQuery();
if((c[m.i][j]
本文档为【分支限界法实现单源最短路径问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483