《分支限界法单源最短路径》由会员分享，可在线阅读，更多相关《分支限界法单源最短路径（9页珍藏版）》请在装配图网上搜索。
1、#include using namespace std;#define MAX 9999/定义无穷大/*Graph类，用以存放有关图的所有信息*/class Graphpublic:/param int初始节点编号/void ShorestPaths(int);void ShowDist();Graph();private:int n;/图的节点个数int *prev;/存放顶点的前驱节点int *c;/存放图的邻接矩阵int *dist;/存放源点到各个顶点的距离;/*节点*/class MinHeapNodefriend class Graph;public:int getI() ret
2、urn i;void setI(int ii)i = ii;int getLength()return length;void setLength(int len)length = len;private:int i;/顶点编号int length;/当前路长 ;/*最小堆*/class MinHeapfriend class Graph;public:MinHeap();MinHeap(int);void DeleteMin(MinHeapNode &);void Insert(MinHeapNode);bool OutOfBounds();private:int length;MinHea
3、pNode *node;Graph:Graph()int wi = 0;int yi = 0;coutn;cout请输入图的邻接矩阵：(无穷大请以9999代替) endl;c = new int*n+1;dist = new intn+1;prev = new intn+1;/初始化邻接矩阵/for (wi = 0; wi = n; wi+)cwi = new intn+1;if (wi = 0)for (yi = 0; yi = n; yi+)cwiyi = 0;elsefor (yi = 0; yi cwiyi;/初始化数组/for (wi = 0; wi = n; wi+)distwi
4、= MAX;prevwi = 0;void Graph:ShowDist()cout 从源点到该节点的最短路径: endl;int i = 0;int temp = 0;for (i = 1; i = n; i+)cout dist i = disti endl;cout ”从源点到终点的最短路径长度为: distn endl;cout 其路径为：；temp = n;while(temp != 0)if (prevtemp = 0)cout (temp);elsecout (temp) - ;temp = prevtemp;cout endl;void Graph:ShorestPaths(i
5、nt v)MinHeap H(n);/最小堆MinHeapNode E;/扩展节点E.i = v;E.length = 0;distv = 0;/搜索问题的解空间树while (true)int j = 0;for (j = 1; j = n; j+)coutcE.ij=cE.ijendl;if (cE.ij != MAX) & (cE.ij != 0)/节点控制关系if (E.length + cE.ij distj)distj = E.length + cE.ij;prevj = E.i;/加入活结点优先队列/若节点为叶子节点，则不加入活结点队列if (j != n)MinHeapNode
6、 N;N.i = j;N.length = distj;H.Insert(N);elseH.DeleteMin(E);if (H.OutOfBounds()break;cout”上一个扩展节点E.i E.lengthendl;H.DeleteMin(E);cout下一个扩展节点E.i E.lengthendl;MinHeap:MinHeap()length = 10;node = new MinHeapNodelength+1;for (int i = 0; i = length; i+)nodei.setI(0);nodei.setLength(0);MinHeap:MinHeap(int
7、n)length = n;node = new MinHeapNodelength+1;for (int i = 0; i = length; i+)nodei.setI(0);nodei.setLength(0);/*取下一个扩展结点，并删除此节点*算法实现其实是用下一个节点的信息替代现有节点的数据*首先在现有的节点中，找出length最短的节点*然后将此节点的数据替换原有的数据*/void MinHeap:DeleteMin(MinHeapNode &E)int i = 0;int j = 0;j = E.getI();/用来删除原来的扩展节点nodej.setI(0);/置零nodej.
8、setLength(0);/置零int temp = MAX;/选择可扩展节点中length域最小的可扩展节点将所选择的扩展节点的数值替换原有的扩展节/点的值，最后在可扩展节点队列中删除原扩展节点，删除方式为：所有域置零/for (i = 1; i = length; i+)if (nodei.getLength() temp) & (nodei.getLength() != 0)E.setI(i);E.setLength(nodei.getLength();temp = nodei.getLength();/temp 中始终为最小值/*加入最小堆*此处添加按节点编号添加，即对应的节点编号添加
9、时*对应队列中相应的编号，即节点5则添加到队列中5号*位置*/void MinHeap:Insert(MinHeapNode N)nodeN.getI().setI(N.getI();nodeN.getI().setLength(N.getLength();/*判断最小堆是否为空*/bool MinHeap:OutOfBounds()int i = 0;bool flag = true;for (i = 1; i = length; i+)if (nodei.getI() != 0)flag = false;return flag;int main()Graph graph;graph.ShorestPaths(l);graph.ShowDist();return 0;亍点3 ?jcI3l-9999c3H2=9999c3H3=2r3H4=53H5=9999从源点到该节点的最短路径：istEU =蚓= 2ist3 = 7ist4 = 4dist5 = 4点到终点的最短路径长度为舛 其商径为：1 请技任意键继续
分支限界法单源最短路径
