●试题六

阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数;a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值;c为二维数组，存储有向网中每一对顶点间的最短路径长度;kay为二维数组，存储最短路径，kay［i］［j］=k表示顶点i 到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有：

Input():输入有向网的顶点数、各条弧及权值，建立带权领接矩阵a。若顶点i到顶点j有弧，则a［i］［j］取弧上的权值，否则a［i］［j］的值取NoEdge。

AllPairs();用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。

OutShortestPath(int i,int j):计算顶点i到顶点j的最短路径。

outputPath(int i,int j):输出顶点i到顶点j的最短路径上的顶点。

Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1，C2，…，Cn,其中C0是已知的带权邻接矩阵，a,Ck(i,j)(0≤i,j＜n)表示从顶点i到顶点j的中间顶点序号不大于k 的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k＜n,有Ck(i,j)=C0(i,j)=a［i］［j］。递推地产生C1，C2，…，Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。

【C++代码】

#include<iostream．h>

＃define NoEdge 10000 //当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示

void Make2DArray(int * * &x,int rows,int cols);

class AdjacencyWDigraph{

private

int n;//有向网中的顶点数目

int**a;//存储顶点间弧上的权值

int**c;//存储计算出的最短路径长度

int**kay;//存储求出的最短路径

pubic:

int Vertices()const {return n;}

void AllPairs();

void Input();//输入有向网的顶点数、各条弧及权值，建立邻接矩阵a

void OutShortestPath(int i,int j);//计算顶点i到j的最短路径(试卷中未列出)

~AdjacencyWDigraph();//析构函数(试卷中未列出)

private:

void outputPath(int i,int j);

};

void AdjacencyWDigraph::AllPairs()

{int i,j,k,t1,t2,t3;

for(i=1;i＜=n;k++)

for(j=1;j＜=n;++j)

{c［i］［j］= (1) ;kay［i］［j］=0;}

for(k=1;k＜=n;k++)

for(i=1;i＜=n;i++){

if(i==k) continue;

t1=c［i］［k］;

for(j=1;j＜=n;j++){

if(j==k||j==i)continue;

t2=c［k］［j］;t3=c［i］［j］;

if(t1!=NoEdge && t2!=NoEdge &&(t3==NoEdge||t1+t2＜t3))

{c［i］［j］= (2) ；kay［i］［j］= (3) ;}

}//for

}//for

}

void AdjacencyWDigraph:: outputPath(int i,int j)

{//输出顶点i到j的最短路径上的顶点

if(i==j)return;

if(kay［i］［j］==0)cout＜＜j＜＜′′;

else { outputPath(i, (4) ); outputPath( (5) );}

}

void Adjacency WDigraph::Input()

{int i,j,u,v,w,E;

cout＜＜″输入网中顶点个数：″;cin＞＞n;

cout＜＜″输入网中弧的个数:″;cin＞＞E;

Make2DArray(a,n+1,n+1);

for(i=1;i＜=n;i++)

for(j=1;j＜=n;j++)a［i］［j］=NoEdge;

for(i=1;i＜=n;i++)a［i］［i］=0;

Make2DArray(c,n+1,n+1);

Make2DArray(kay,n+1,n+1);

for(i=1;i＜=E;i++){

cout＜＜″输入弧的信息(起点终点权值)：″；cin＞＞u＞＞v＞＞w;a［u］［v］=w;

}

}

void Make2DArray(int**&x,int rows,int cols)

{int i,j;

x=new int*［rows+1］;

for(i=0;i＜rows+1;i++)x［i］=new int ［cols+1］;

for(i=1;i＜=rows;i++)

for(j=1;j＜=cols;j++＝x［i］［j］=0;

}