【说明】[程序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;//记录源点到本顶点的当前最短路径的长度，源点到自身的长度为0}template＜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 whilefor(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；}
参考答案：
解析： (1)this-＞length或(*this).length 操作符，的成员函数，比较两个对象的最短路径的长度length，大于则返回真(1)。 (2)new EdgeType[MaxNumVertex] 动态申请EdgeType类的对象数组distance，长度为MaxNumVertex，存放最短路径的长度。 (3)E(source，0) 定义最小化堆模板类MinNode＜VertexType, EdgeType＞的对象E(source，0)。 (4)E.length+ AdjMatrix [E. VcxNum* MaxNumVertex+j] 若E.length+ AdjMatrix [E.VexNum*MaxNumVertex+j]小于distance[j]，则distance[j]取这个更小值。 (5)N(j，distance[j]) 定义最小化堆模板类MinNode＜VertexType，EdgeType＞的对象N(j，distance[j])。