阅读下列C＋＋程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】[程序6说明]单源最短路径的

Question

阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。

【说明】[程序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 while

for(k=0；k＜MaxNumVertex；k++){

cout＜＜"Shorstest path from vertex"＜＜k＜＜"is"＜＜distance[k]＜＜end1；

j=k；cou

Answer 1

正确答案：(1)this-＞length或(*this).length (2)new EdgeType[MaxNumVertex] (3)E(source0) (4)E.length+ AdjMatrix [E. VcxNum* MaxNumVertex+j] (5)N(jdistance[j])
(1)this-＞length或(*this).length (2)new EdgeType[MaxNumVertex] (3)E(source，0) (4)E.length+ AdjMatrix [E. VcxNum* MaxNumVertex+j] (5)N(j，distance[j]) 解析：(1)this-＞length或(*this).length
操作符，的成员函数，比较两个对象的最短路径的长度length，大于则返回真(1)。
(2)new EdgeType[MaxNumVertex]
动态申请EdgeType类的对象数组distance，长度为MaxNumVertex，存放最短路径的长度。
(3)E(source，0)
定义最小化堆模板类MinNodeVertexType, 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])
定义最小化堆模板类MinNodeVertexType，EdgeType＞的对象N(j，distance[j])。