多项选择题【说明】[程序6说明]单源最短路径的分支限界算法。const int MAXNUM=29999；#include＜iostream＞#include＜vector＞#include＜algorithm＞#include＜functional＞using namespace std；template ＜class VertexType,class EdgeType＞class MinNode 程序中使用的最小化堆的结点说明friend class Graph＜VertexType,EdgeType＞public:MinNode (int nl, EdgeType length1) VexNum=nl；length=length1；bool operator＞(const MinNode＜VertexType,EdgeType＞&p)const return (1) ＞p.length；private: int VexNum; 记录源点序号，序号数组p及distance下标相一致。源点为初始扩展顶点 EdgeType length; 记录源点到本顶点的当前最短路径的长度，源点到自身的长度为0template＜class VertexType,classEdgeType＞void Graph＜VertexType,EdgeType＞:: shortestpath(VertexType start) int j,k,source; source 记录源点的序号。 EdgeType*distance= (2) ； int*p=new int[MaxNumVertex]; vector＜MinNode＜VertexType,EdgeType＞ ＞H； for(source=0；source＜MaxNumVertex;source++) if(NodeList[source]==start)break； if (source＞=MaxNumVertex)cout＜＜”This is error!”＜＜end1；return； MinNode＜VertexType,Edge Type＞ (3) ； for(k=0；k＜MaxNumVertex；k++) distance[k]：MAXXUM； 记录源点到本顶点k的最终的最短路径的长度 p[k]=source； 记录最短路径上的本顶点的直接前驱顶点的序号 distance[source]=0；p[source]=-1； m 是源点，前一顶点不存在 vector＜MinNode＜VertexType, EdgeType＞＞::iterator q； while(1) for(j=0；j＜MaxNumVertex；j++) if((AdjMatrix[E.VexNum* MaxNumVertex+j]＜MAXNUM) &&( (4) ＜distance[j])) distance[j]=E.length+AdjMatrix[E.VexNum* MaxNumVertex+j]； p[j]=E. VexNum； 记录顶点j的前一顶点 MinNode＜VertexType, EdgeType＞ (5) ； H．push_ back(N)； push_heap(H. begin()，H.end()，greater＜MinNode＜VertexType， EdgeType＞＞())； if(H.empty()＝true)break； 若优先队列为空，那么算法结束 else pop_ heap(H.begin()，H. end()，greater＜MinNode＜VertexType， EdgeType＞＞())； q=H.end()-1； 从最小化堆中取路径最短的顶点 E=*q； H.pop_ back()； 删除从最小化堆中“挤”出的顶点 end while for(k=0；k＜MaxNumVertex；k++) cout＜＜ Shorstest path from vertex ＜＜k＜＜ is ＜＜distance[k]＜＜end1； j=k；cout＜＜ All vertices are： ； while(j!=source)cout＜＜j＜＜ -＞ ；j=p[j]； cout＜＜source＜＜”.”＜＜end1； 打印顶点的最短路径长度和至源点的最短路径上经过的顶点序列 return；
【说明】[程序6说明]单源最短路径的分支限界算法。
const int MAXNUM=29999；
#include＜iostream＞
#include＜vector＞
#include＜algorithm＞
#include＜functional＞
using namespace std；
template ＜class VertexType,class EdgeType＞
class MinNode //程序中使用的最小化堆的结点说明
friend class Graph＜VertexType,EdgeType＞
public:
MinNode (int nl, EdgeType length1)
VexNum=nl；
length=length1；bool operator＞(const MinNode＜VertexType,EdgeType＞&p)const
return (1) ＞p.length；private:
int VexNum;
//记录源点序号，序号数组p及distance下标相一致。源点为初始扩展顶点
EdgeType length;
//记录源点到本顶点的当前最短路径的长度，源点到自身的长度为0template＜class VertexType,classEdgeType＞
void Graph＜VertexType,EdgeType＞:: shortestpath(VertexType start)
int j,k,source;//source 记录源点的序号。
EdgeType*distance= (2) ；
int*p=new int[MaxNumVertex];
vector＜MinNode＜VertexType,EdgeType＞ ＞H；
for(source=0；source＜MaxNumVertex;source++)
if(NodeList[source]==start)break；
if (source＞=MaxNumVertex)cout＜＜”This is error!”＜＜end1；return；
MinNode＜VertexType,Edge Type＞ (3) ；
for(k=0；k＜MaxNumVertex；k++)
distance[k]：MAXXUM； //记录源点到本顶点k的最终的最短路径的长度
p[k]=source； //记录最短路径上的本顶点的直接前驱顶点的序号
distance[source]=0；p[source]=-1；//m 是源点，前一顶点不存在
vector＜MinNode＜VertexType, EdgeType＞＞::iterator q；
while(1)
for(j=0；j＜MaxNumVertex；j++)
if((AdjMatrix[E.VexNum* MaxNumVertex+j]＜MAXNUM)
&&( (4) ＜distance[j]))
distance[j]=E.length+AdjMatrix[E.VexNum* MaxNumVertex+j]；
p[j]=E. VexNum； //记录顶点j的前一顶点
MinNode＜VertexType, EdgeType＞ (5) ；
H．push_ back(N)；
push_heap(H. begin()，H.end()，greater＜MinNode＜VertexType，
EdgeType＞＞())；
if(H.empty()＝true)break； //若优先队列为空，那么算法结束
else
pop_ heap(H.begin()，H. end()，greater＜MinNode＜VertexType，
EdgeType＞＞())；
q=H.end()-1； //从最小化堆中取路径最短的顶点
E=*q；
H.pop_ back()； //删除从最小化堆中“挤”出的顶点
//end while
for(k=0；k＜MaxNumVertex；k++)
cout＜＜"Shorstest path from vertex"＜＜k＜＜"is"＜＜distance[k]＜＜end1；
j=k；cout＜＜"All vertices are："；
while(j!=source)cout＜＜j＜＜"-＞"；j=p[j]；
cout＜＜source＜＜”.”＜＜end1；
//打印顶点的最短路径长度和至源点的最短路径上经过的顶点序列
return；
